luogu4366 [Code+#4]最短路[优化建边最短路]

luogu4366 [Code+#4]最短路[优化建边最短路]

显然这里的$n^2$级别的边数不能全建出来,于是盯住xor这个关键点去 瞎猜 探究有没有什么特殊性质可以使得一些边没有必要建出来。

发现一个点经过一次xor $x$,花费$x$这么多代价(先不看$C$),到达另一个点$u\text{xor}x$。

结合异或性质,发现其实这个过程完全可以通过把$x$拆成一位一位去分别xor上$u$,也就是说,任何一个点到达另一个点只需要不断走$2^i$这种xor值就可以到达,于是每个点连出$logn$条边,分别和其序号二进制位每一位异或一个1的数相连。这样,如果要走一条xor路径,就可以拆成走若干条上述简化路径。于是建边就可以得到简化,总边数$m+n\text{log}n$,然后跑最短路即可。。

注意一个RE了无数发的detail:食用上述建边方法需要注意有部分超出$n$但小于$2^{log(n)+1}$的点建的边以及$0$号点连的边也是要考虑进去的,具体为什么自己想。。。于是乎这个数组大小不能照1e5来开了,开两倍2e5。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define dbg(x) cerr << #x << " = " << x <<endl
 8 using namespace std;
 9 typedef long long ll;
10 typedef double db;
11 typedef pair<ll,int> pii;
12 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
13 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
14 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
15 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
16 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
17 template<typename T>inline T read(T&x){
18     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
19     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
20 }
21 const int N=1e5+7,M=3000000+7;
22 struct thxorz{int to,nxt,w;}G[M];
23 int Head[N<<1],tot;
24 int n,m,c,len,s,t;
25 inline void Addedge(int x,int y,int z){G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot,G[tot].w=z;}
26 ll dis[N<<1];
27 priority_queue<pii,vector<pii>,greater<pii> >q; 
28 #define y G[j].to
29 inline void dij(){
30     memset(dis,0x3f,sizeof dis);q.push(make_pair(dis[s]=0,s));
31     while(!q.empty()){
32         ll d=q.top().first;int x=q.top().second;q.pop();
33         if(t==x)break;
34         if(d^dis[x])continue;
35         for(register int j=Head[x];j;j=G[j].nxt)if(MIN(dis[y],d+G[j].w))q.push(make_pair(dis[y],y));
36     }
37 }
38 #undef y
39 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
40     read(n),read(m),read(c);
41     for(register int i=1,x,y,z;i<=m;++i)read(x),read(y),read(z),Addedge(x,y,z);
42     len=__lg(n);read(s),read(t);
43     for(register int i=0;i<=(1<<len+1)-1;++i)for(register int j=len;~j;--j)Addedge(i,i^(1<<j),(1<<j)*c);
44     dij();
45     return printf("%lld\n",dis[t]),0;
46 }
View Code

总结:对于边过多的图尝试发掘性质简化建边,去除没有必要的边,用如前缀/异或/线段树等方法来降低边数或者用少量边替代全部情况。