题意： 给定n个点，求从s到t的最短路径，其中有两种走法（可以混搭）：一种是走给定的m有向边(ui,vi,wi)；另一种可以由任意点x到任意点y，其费用是c∗(x xor y)
朴素的建法是O(n^2+m)的.然而事实上一个从x->y权值为w的边是可以被其他边取代的，我们可以把x拆成二进制，一位一位的修改最终到达y，此时经过的权值显然也是w。
举个例子：
假设我们要从 001（2）? 到 010（2）?，我们要花费 2^0 + 2^1 的费用； 但是，最短路有一个 优越的性质，我们可以把边拆开来，可以先从 001（2）? 到 000（2），再从 000（2）? 到 010（2），费用是一样的。
也就是说，对于一个点x，我们只需要让他和x*2^k连边即可，这样就优化为O(nlogn+m)了，跑一遍dij就好了。
代码：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <queue> 6 #include <cmath> 7 using namespace std; 8 int n,m,c,st,sd,x,y,val; 9 struct node{ 10 int to,next,w; 11 }ed[5000005]; 12 int dis[5000005],vis[5000005],head[5000005],cnt; 13 inline void add(int u,int v,int w){ 14 ed[++cnt].next=head[u]; 15 ed[cnt].to=v; 16 ed[cnt].w=w; 17 head[u]=cnt; 18 } 19 inline int read(){ 20 int x = 1,a = 0; 21 char ch = getchar(); 22 while(ch < ‘0‘ || ch > ‘9‘){ 23 if(ch == ‘-‘)x = -1; 24 ch = getchar(); 25 } 26 while(ch <= ‘9‘&&ch >= ‘0‘){ 27 a = a * 10 + ch - ‘0‘; 28 ch = getchar(); 29 } 30 return x*a; 31 } 32 priority_queue<pair<int,int> > q; 33 inline void Dij(int s){ 34 q.push(make_pair(0,s));memset(vis,0,sizeof(vis));memset(dis,63,sizeof(dis));dis[s]=0; 35 while (!q.empty()){ 36 int x = q.top().second; 37 q.pop(); 38 if (vis[x]) continue; 39 vis[x]=1; 40 for (register int i = head[x];i;i=ed[i].next){ 41 int to = ed[i].to; 42 if (dis[to]>dis[x]+ed[i].w){ 43 dis[to]=dis[x]+ed[i].w; 44 q.push(make_pair(-dis[to],to)); 45 } 46 } 47 } 48 return; 49 } 50 int main(){ 51 n=read();m=read();c=read(); 52 for (int i = 1;i <= m;i++){ 53 x=read(),y=read(),val=read(); 54 add(x,y,val); 55 } 56 int lgn = floor(log2(n)) + 1; 57 n = (1 << lgn) - 1; 58 for (register int i = 1;i <= n;i++) 59 for (register int j = 0;j < lgn;j++) 60 add(i,i^(1<<j),(1<<j)*c); 61 st=read(),sd=read(); 62 Dij(st); 63 cout<<dis[sd]; 64 }
原文：https://www.cnblogs.com/very-beginning/p/12732809.html