感谢sinian阿姨的热心指导
Description
这篇好久前写的，现在只是转过来，忘了
Solution
假设 $a leq b$
最小生成树上$a$边尽量要多，若a边不够将全图联通才用$b$边
所以可以用$a$边将图连成多个联通块，再用$b$边将全图联通
路径只要求在最小生成树上，且到不同点的最短路可以在不同生成树上
因此单个联通块内一点到另一点的最短路一定在某棵最小生成树上
用$b$边打通需要注意
1.$b$边两端不在同一联通块内（在同一联通块内的$b$边显然不会在最小生成树上，与它构成环的$a$边都比它小）
2.不能通过$b$边绕一圈回到同一联通块内，即不能重复经过同一联通块，想到状压
但$N leq 70$无法直接状压
考虑这样的性质
单个联通块内点数 $leq 3$, 任意两点间距离 $leq 2a$, 若绕一圈回来至少需要两条$b$边，则绕一圈回来距离 $geq 2b$, 不可能再去更新原来两点间距离，所以可以忽略联通块点数 $leq 3$的部分
时间复杂度:$O(2^N(N + M))$
空间复杂度:$O(2^NN)$
Code
#include <bits/stdc++.h> using namespace std; inline int read() { int out = 0; register char cc = getchar(); while (cc < '0' || cc > '9') cc = getchar(); while (cc >= '0' && cc <= '9') out = (out << 3) + (out << 1) + (cc ^ 48), cc = getchar(); return out; } int N, M, a, b, x, y, z, dist[71][1 << 18], check[71][1 << 18], ans[71]; int Id[80], tim; queue<int> q1, q2, s1, s2; int head[210], nxt[410], to[410], edge[410], cnt; void add(int u, int v, int w) { to[++cnt] = v; edge[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; } int fa[80], tot[80]; int find(int k) { return fa[k] == k ? k : fa[k] = find(fa[k]); } void Merge(int x, int y) { int rx = find(x), ry = find(y); if (rx != ry) fa[rx] = ry, tot[ry] += tot[rx]; } int main() { N = read(), M = read(), a = read(), b = read(); if (a > b) swap(a, b); // 保证 a < b for (int i = 1; i <= N; i++) fa[i] = i, Id[i] = -1, tot[i] = 1, ans[i] = 0x3f3f3f3f; for (int i = 1; i <= M; i++) { x = read(), y = read(), z = read(); if (z == a) Merge(x, y); // 用a边合并联通块 add(x, y, z); add(y, x, z); } for (int i = 1; i <= N; i++) if (Id[i] == -1 && tot[find(i)] > 3) { for (int j = 1; j <= N; j++) if (find(i) == find(j)) Id[j] = tim; ++tim; } // 给联通块标号(从0~tim-1) for (register int i = 1; i <= N; i++) for (register int S = 0; S < (1 << tim); S++) dist[i][S] = 0x3f3f3f3f; dist[1][1 << Id[1]] = 0; q1.push(1); s1.push(Id[1] != -1 ? 1 << Id[1] : 0); while (!q1.empty() || !q2.empty()) { int u, S, S1, S2; x = y = 0x3f3f3f3f; if (!q1.empty()) x = q1.front(), S1 = s1.front(); if (!q2.empty()) y = q2.front(), S2 = s2.front(); if (x == 0x3f3f3f3f) u = y, S = S2, q2.pop(), s2.pop(); else if (y == 0x3f3f3f3f) u = x, S = S1, q1.pop(), s1.pop(); else if (dist[x][S1] < dist[y][S2]) u = x, S = S1, q1.pop(), s1.pop(); else u = y, S = S2, q2.pop(), s2.pop(); // 奇奇怪怪的最短路 // 图上边权仅有 a, b // 将以a边更新得到的点与b边更新得到分装两个队列 // 每次取较小的更新其它点 // 据洛谷上巨佬说可以把复杂度降到O(N + M) check[u][S] = false; for (int i = head[u]; i; i = nxt[i]) { int v = to[i], w = edge[i]; if (w == a && dist[v][S] > dist[u][S] + w) { dist[v][S] = dist[u][S] + w; if (!check[v][S]) q1.push(v), s1.push(S), check[v][S] = true; } if (w == b) { if (find(u) == find(v)) continue; if (Id[v] != -1 && ((1 << Id[v]) & S)) continue; int Next = (Id[v] != -1 ? S | (1 << Id[v]) : S); if (dist[v][Next] > dist[u][S] + w) { dist[v][Next] = dist[u][S] + w; if (!check[v][Next]) q2.push(v), s2.push(Next), check[v][Next] = true; } } } } for (register int i = 1; i <= N; i++) for (register int S = 0; S < 1 << tim; S++) if (ans[i] > dist[i][S]) ans[i] = dist[i][S]; for (int i = 1; i <= N; i++) cout << ans[i] << ' '; return 0; }