本题就是求两点间只经过n条边的最短路径，定义广义的矩阵乘法，就是把普通的矩阵乘法从求和改成了取最小值，把内部相乘改成了相加。

代码包含三个内容：广义矩阵乘法，矩阵快速幂，离散化；

1 #include
2 using namespace std;
3 const int INF=0x3f3f3f3f;
4 const int N=120;
5 int Hash[1000005],cnt=0;//用于离散化
6 struct matrix{
7 int m[N][N];
8 }ans,a;
9
10 matrix operator*(const matrix& a,const matrix& b){//定义广义矩阵乘法
11 matrix c;
12 memset(c.m,INF,sizeof(c.m));
13 for(int i=1;i<=cnt;i++) 14 for(int j=1;j<=cnt;j++) 15 for(int k=1;k<=cnt;k++) 16 c.m[i][j]=min(c.m[i][j],a.m[i][k]+b.m[k][j]); 17 return c; 18 } 19 20 matrix pow_matrix(matrix a,int n){ 21 ans=a; 22 n--;//矩阵初值ans=M 23 while(n){ 24 if(n&1) ans=ans*a; 25 a=a*a; 26 n>>=1;
27 }
28 return ans;
29 }
30
31 int main(){
32 int n,t,s,e;
33 scanf("%d%d%d%d",&n,&t,&s,&e);
34 memset(a.m,INF,sizeof(a.m));
35 while(t--){
36 int u,v,w;
37 scanf("%d%d%d",&w,&u,&v);
38 if(!Hash[u]) Hash[u]=++cnt;
39 if(!Hash[v]) Hash[v]=++cnt;//对点离散化
40 a.m[Hash[u]][Hash[v]]=a.m[Hash[v]][Hash[u]]=w;//邻接矩阵存图思想
41 }
42 ans=pow_matrix(a,n);
43 printf("%d",ans.m[Hash[s]][Hash[e]]);
44 return 0;
45 }