luoguP4366 [Code+#4]最短路 最短路
好久没写过博客了....
本题还是挺有趣的(很水的最短路)
关键在于怎么优化这$n^2$条连边
通常，我们希望用一些边来替代一条边从而减小边集
那么，注意到异或操作可以拆分成按位运算，因此我们只需考虑$i$和每一位异或的结果连边即可
由于我们由$i$转移到$j$时，有可能中间节点$i wedge t$是比$i$大的
因此，实际上我们应该带着$2^t$个点跑最短路，其中$2^t geqslant n$
然后就没什么了...
#include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; extern inline char gc() { static char RR[23456], *S = RR + 23333, *T = RR + 23333; if(S == T) fread(RR, 1, 23333, stdin), S = RR; return *S ++; } inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } #define sid 300050 #define eid 8005000 #define ll long long #define ri register int int n, m, c, cnp; int vis[sid], cap[sid], nxt[eid], fee[eid], node[eid]; inline void addedge(int u, int v, int w) { nxt[++ cnp] = cap[u]; cap[u] = cnp; node[cnp] = v; fee[cnp] = w; } ll dis[sid]; struct P { int id; ll dis; friend bool operator < (P a, P b) { return a.dis > b.dis; } }; priority_queue <P> q; #define cur node[i] void dij(int s, int t) { memset(dis, 127, sizeof(dis)); dis[s] = 0; q.push((P){ s, 0 }); while(!q.empty()) { int id = q.top().id; ll di = q.top().dis; q.pop(); if(vis[id]) continue; vis[id] = 1; for(ri i = cap[id]; i; i = nxt[i]) if(dis[cur] > di + fee[i]) dis[cur] = di + fee[i], q.push((P){ cur, dis[cur] }); } printf("%lld ", dis[t]); } int main() { n = read(); m = read(); c = read(); for(ri i = 1; i <= m; i ++) { int u = read(), v = read(), w = read(); addedge(u, v, w); } int N = 1; while(N <= n) N <<= 1; for(ri i = 1; i <= N; i ++) for(ri j = 1; j <= N; j <<= 1) addedge(i, i ^ j, j * c); int s = read(), t = read(); dij(s, t); return 0; }