解析：这道题本质上是求两点之间经过n条边的最短路，是一道快速幂的应用，只需把快速幂自乘的操作改成最短路边数*2，把快速幂乘答案的操作改成维护答案即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<cstring> 5 using namespace std; 6 int minn[1005][1005],b[1005][1005],c[1005][1005],n,t,s,e,num,ans[1005][1005],x,y,z,p[1000001],number[1000001]; 7 bool vis[1000001]; 8 int main() 9 { 10 memset(b,999999,sizeof(b)); 11 memset(ans,999999,sizeof(ans)); 12 memset(c,999999,sizeof(c)); 13 cin>>n>>t>>s>>e; 14 for(int i=1;i<=t;i++) 15 { 16 cin>>z>>x>>y; 17 if(!vis[x])p[++num]=x,vis[x]=1,number[x]=num; 18 if(!vis[y])p[++num]=y,vis[y]=1,number[y]=num; 19 b[number[x]][number[y]]=b[number[y]][number[x]]=z; 20 } 21 for(int i=1;i<=num;i++)ans[i][i]=0; 22 while(n>0) 23 { 24 if(n&1) 25 { 26 memset(minn,999999,sizeof(minn)); 27 for(int k=1;k<=num;k++) 28 for(int i=1;i<=num;i++) 29 for(int j=1;j<=num;j++) 30 minn[i][j]=min(minn[i][j],ans[i][k]+b[k][j]); 31 memcpy(ans,minn,sizeof(ans)); 32 } 33 memset(c,999999,sizeof(c)); 34 for(int k=1;k<=num;k++) 35 for(int i=1;i<=num;i++) 36 for(int j=1;j<=num;j++) 37 c[i][j]=min(c[i][j],b[i][k]+b[k][j]); 38 memcpy(b,c,sizeof(b)); 39 n>>=1; 40 } 41 cout<<ans[number[s]][number[e]]; 42 return 0; 43 }