@loj - 6354@「CodePlus 2018 4 月赛」最短路

目录

@description@@solution@@accepted code@@details@

---

@description@

企鹅国中有 N 座城市，编号从 1 到 N 。

对于任意的两座城市 i 和 j ，企鹅们可以花费 (i xor j) * C 的时间从城市 i 走到城市 j ，这里 C 为一个给定的常数。

当然除此之外还有 M 条单向的快捷通道，第 i 条快捷通道从第 Fi 个城市通向第 Ti 个城市，走这条通道需要消耗 Vi 的时间。

现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 A 前往城市 B 最少需要多少时间？

input 输入第一行包含三个整数 N, M, C (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 3*10^5, 1 ≤ C ≤ 100)，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数 C。

接下来的 M 行，每行三个正整数 Fi, Ti, Vi (1 ≤ Fi ≤ N, 1 ≤ Ti ≤N, 1 ≤ Vi ≤ 100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

最后一行两个正整数 A, B，表示企鹅豆豆选择的起点城市标号和终点城市标号。

output 输出一行一个整数，表示从城市 A 前往城市 B 需要的最少时间。

simple input 7 2 10 1 3 1 2 4 4 3 6simple output 34simple explain 先从 3 走到 2 ，再从 2 通过通道到达 4 ，再从 4 走到 6。

@solution@

令人自闭（事实上是因为自己太弱的）的一道题 TAT。

我们有两类边：一般边 与 异或边。 一种特别暴力的想法就是，按题意给所有点之间连上这两类边，跑从 A 出发到 B 的最短路。但是由于异或边构成的是完全图，导致这种想法并不可行。

然而我们注意到一般边的数量是在正常范围以内。而且我们可不可以利用异或的什么性质来简化图，减少异或边的数量？

这个时候就可以用位运算最基本的套路：拆位。即把二进制表示下的每一位分类讨论。 对于 i 到 j 的异或边，它的费用为 i xor j。我们将 i xor j 拆成若干个 2 的幂之和，对应到图上，即将 i 到 j 的异或边拆成若干个费用为 2 的幂的边组成的路径。

具体怎么搞呢？我们对于结点 i，只连出 i xor 2^0, i xor 2^1, ... 共 log 条边。这样， i 到 j 的最短路径就对应着原图中 i 到 j 的异或边。 而边数降低为 O(nlog n + M) 条，就可以该怎么跑最短路就怎么跑（当然 SPFA 还是该怎么卡就怎么卡）。

注意原本的点编号是 1~N，而新图必须拓展到 0~2^p (2^p > N) 拆位才不会拆出问题来。

@accepted code@

#include<cstdio> #include<queue> using namespace std; const int MAXN = 200000; const int MAXM = 500000; const int INF = (1<<30); struct edge{ int to, dis; edge *nxt; }edges[MAXM + 20*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0]; void addedge(int u, int v, int w) { edge *p = (++ecnt); p->to = v, p->dis = w; p->nxt = adj[u], adj[u] = p; } int dist[MAXN + 5], tot; bool vis[MAXN + 5]; struct node{ int pos, dis; node(int _p=0, int _d=0):pos(_p), dis(_d){} }; bool operator < (node a, node b) { return a.dis > b.dis; } priority_queue<node>que; void dijkstra(int S) { que.push(node(S, 0)); for(int i=0;i<=tot;i++) dist[i] = INF, vis[i] = false; dist[S] = 0; while( !que.empty() ) { node t = que.top(); que.pop(); if( vis[t.pos] ) continue; vis[t.pos] = true; for(edge *p=adj[t.pos];p!=NULL;p=p->nxt) { if( t.dis + p->dis < dist[p->to] ) { dist[p->to] = t.dis + p->dis; que.push(node(p->to, dist[p->to])); } } } } int main() { int N, M, A, B, C; scanf("%d%d%d", &N, &M, &C); for(int i=1;i<=M;i++) { int F, T, V; scanf("%d%d%d", &F, &T, &V); addedge(F, T, V); } scanf("%d%d", &A, &B); for(tot = 1;tot <= N;tot <<= 1); for(int i=0;i<tot;i++) for(int p=1;p<tot;p<<=1) addedge(i, i^p, p*C); dijkstra(A); printf("%d\n", dist[B]); }

@details@

自己在做这道题的时候，发现连续通过两条异或边是不优秀的，因为 (i xor j + j xor k) * C >= (i xor j xor j xor k) * C = (i xor k) * C。然后就顺着这个方向走了好久…… 好像有想到过拆位，然后一瞬间走神就忘记了…… 我太弱了 TAT。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/10213571.html

相关资源：垃圾分类数据集及代码