题意就是给一张无向有边权的图、起点、终点，求起点到终点经过n条边的最短路。n<=10^6，点的编号<=10^3，边数<=10^2。
这个边数让人不由自主地想到了floyd，然后发现floyd每次相当于加入了一个点（注意，这里的“一次”也是O(点数^3)的，但是在这一次floyd的过程中不会更新结果。）也就是说，第一次floyd求出来了两点之间只走一条边的最短路，第二次求出来了两点之间只走两条边的最短路……，第n次求出来了只走n条边的最短路。这时候就会发现，n遍不在过程中更新答案的floyd后，答案就出来了。
好不容易推到了这一步，发现了n<=10^6的数据范围，想必心中是有些崩溃的。但是邻接矩阵是什么？是矩阵！这样就可以思考用矩阵快速幂的方法。发现floyd的转移时c[i][j] = min { dis[i][k] + dis[k][j] | i,k,j为图中点的编号}，和矩阵快速幂的转移有点像，而且转移时也是上一步求出的答案对于最初的邻接矩阵作运算。这时就可以考虑用一些不对劲的方法改造矩阵乘法。
将矩阵快速幂中的乘法改成上面那样的转移方法，就会发现只要求出邻接矩阵^n就好了。
这样就完了？当然不是。
题目中，点的编号<=10^3，直接floyd肯定会时间超限。注意到边数<=10^2，而每条边顶多连两个与之前不同的点，那么出现的不同的点顶多有200个。将点进行离散化就解决了。
还有一些细节，编的时候都能想得到，在这就不多说了。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<iomanip> #include<cstdlib> using namespace std; typedef struct node{ int mat[210][210]; }Matrix; Matrix rd,dis; int n,t,s,e,siz,mc[1010]; int read(){ int x=0,f=1; char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1; while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } Matrix mul(Matrix a,Matrix b){ Matrix c; memset(c.mat,0x3f,sizeof(c.mat)); for(int k=1;k<=siz;k++){ for(int i=1;i<=siz;i++){ for(int j=1;j<=siz;j++){ c.mat[i][j]=min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]); } } } return c; } void pow(int tim){ while(tim) { if(tim&1) rd=mul(rd,dis); dis=mul(dis,dis); tim>>=1; } } int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); n=read(),t=read(),s=read(),e=read(); memset(rd.mat,0x3f,sizeof(rd.mat)); memset(dis.mat,0x3f,sizeof(dis.mat)); memset(mc,-1,sizeof(mc)); for(int i=1;i<=t;i++){ int w=read(),u=read(),v=read(); if(mc[u]==-1)mc[u]=++siz; if(mc[v]==-1)mc[v]=++siz; u=mc[u],v=mc[v]; dis.mat[v][u]=min(dis.mat[u][v],w); dis.mat[u][v]=min(dis.mat[u][v],w); } for(int i=1;i<=siz;i++){ rd.mat[i][i]=0; } pow(n); cout<<rd.mat[mc[s]][mc[e]]; return 0; }