「luogu4366」最短路

传送门

直接连边显然不行，考虑优化。

根据异或的结合律和交换律等优秀性质，我们每次只让当前点向只有一位之别的另一个点连边，然后就直接跑最短路。

注意点数会很多，所以用配对堆优化 \(\text{Dijkstra}\) 即可。

参考代码：

#include <cstring>

#include <cstdio>

#include <ext/pb_ds/priority_queue.hpp>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

using namespace __gnu_pbds;

const int _ = 1e6 + 10, __ = 3e6 + 10;

int tot, head[_], nxt[__], ver[__], w[__];

inline void Add_edge(int u, int v, int d)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, w[tot] = d; }

int n, m, c, s, t, dis[_], vis[_];

struct node { int val, u; } ;

inline bool operator < (const node& x, const node& y) { return x.val > y.val; }

priority_queue < node > Q;

inline void Dijkstra() {

	memset(dis, 0x3f, sizeof dis);

	Q.push((node) { 0, s }), dis[s] = 0;

	while (!Q.empty()) {

		int u = Q.top().u; Q.pop();

		if (vis[u]) continue ; vis[u] = 1;

		for (rg int i = head[u]; i; i = nxt[i]) {

			int v = ver[i];

			if (dis[v] > dis[u] + w[i])

				dis[v] = dis[u] + w[i], Q.push((node) { dis[v], v });

		}

	}

}

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	read(n), read(m), read(c);

	for (rg int u, v, d; m--; )

		read(u), read(v), read(d), Add_edge(u, v, d);

	for (rg int i = 1; i <= 100000; ++i)

		for (rg int j = 0; j <= 16; ++j) Add_edge(i, i ^ (1 << j), (1 << j) * c);

	read(s), read(t);

	Dijkstra();

	printf("%d\n", dis[t]);

	return 0;

}

巴特西

「luogu4366」最短路

「luogu4366」最短路

最新文章

热门文章