(\)
(Description)
一张点的编号为(1 ext~N)的有向图，初始给出 (M) 条边，有边权。其次还存在大量的边，其形式是：
对于任意两个编号分别为 (i,j) 的两个点，其之前存在一条边权为 ((ioplus j) imes C) 的边。
求 (A) 号点到 (B) 号点的最短路长度。
- (Nle10^5,Mle 5 imes10^5,Cle 100)
(\)
(Solution)
(N^2) 建边显然空间时间都承受不住，考虑能否优化这个过程。
假如如此构造现在有一条从 (2) 到 (5) 的边，显然这个边权是
[(111)_2 imes C
]
那么我们观察图中的边，显然存在如下几条：
[2
ightarrow 0:w=(010)_2 imes C\
0
ightarrow 4:w=(100)_2 imes C\
4
ightarrow 5:w=(001)_2 imes C
]
有没有发现，走这三条路的权值和其实等价于走原来那一条路？
于是有了一个简单的做法：按照二进制位分开考虑。
也就是说，我们对于每一个点，除去给出的 (M) 条边外，只连出去边长为 (2) 的整次幂的边。
为什么这样建边等价于原来的图？因为我们每次只走二进制位里的一个 (1) ，最后走的总路径长度不变。
然后边的级别就是 (NlogN+M)，存的下，跑个(Dij) 开个 (O2) 能过。
注意这个转移过程中我们经过的点的编号可能会超出(N)，所以我们要把 (N) 加大到第一个 (ge N) 的 (2) 的幂，同时注意这些新加的点也要把对应的 (log) 条边建出来，否则就可能无法转移了。
(\)
(Code)
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200010
#define M 3000010
#define R register
#define gc getchar
using namespace std;
typedef long long ll;
int n,m,c,s,t,tot,bit,hd[N],dis[N];
bool vis[N];
struct edge{int to,nxt,w;}e[M];
inline void add(int u,int v,int w){
e[++tot].to=v; e[tot].w=w;
e[tot].nxt=hd[u]; hd[u]=tot;
}
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
priority_queue<pair<int,int> > q;
inline void dij(){
memset(dis,0x3f,sizeof(dis));
dis[s]=0; q.push(make_pair(0,s));
R int u;
while(!q.empty()){
u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=1;
for(R int i=hd[u],v;i;i=e[i].nxt)
if(dis[v=e[i].to]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
q.push(make_pair(-dis[v],v));
}
}
printf("%d
",dis[t]);
}
int main(){
n=rd(); m=rd(); c=rd();
bit=log2(n)+1; n=(1<<bit)-1;
for(R int i=1,u,v,w;i<=m;++i){
u=rd(); v=rd(); w=rd(); add(u,v,w);
}
for(R int i=0;i<=n;++i)
for(R int j=0;j<bit;++j) add(i,i^(1<<j),c*(1<<j));
s=rd(); t=rd(); dij();
return 0;
}