题目
（直接放简陋中文翻译版了……）给定一张 (T) 条边的无向连通图，求从 (S) 到 (E) 经过 (N) 条边的最短路长度。
解说
首先洛谷橙名祭！切题177道，社区贡献值43，排名1.52k，正式橙名！(゜-゜)つロ 干杯~
之后我们来看这道题。看完之后第一反应(DFS)不香吗？直接莽(DFS)！10分钟写了个(DFS)，结果可以想象(T)的很惨……
还能怎么办呢？求最短路的方法里能控制经过(N)个点而且比较容易优化的好像只有(Floyd)了，可以用矩阵快速幂优化。
总体思路：
首先，我们有两个矩阵，如果其中一个矩阵代表恰好经过(x)条边的最短路，另外一个矩阵代表恰好经过(y)条边的最短路。那么将这两个矩阵合并就代表恰好经过(x+y)条边的最短路。怎么合并呢？结合下面这个式子理解一下：
(c[i][j]=min(c[i][j],a[i][k]+b[k][j]));
其中(i,j,k)就是(Floyd)三层循环里的(i,j,k);而(a)矩阵是经过(x)条边的最短路，(b)矩阵是经过y条边的最短路，那么(c)矩阵就是我们得到的经过(x+y)条边的最短路了。
那么我们依据初始输入的数组（也就是只经一条边两个点的距离）,这样转移(n-1)((1+(n-1);2+(n-2);cdotscdots))次，就可以得出我们想要的答案了。
之前说了矩阵快速幂优化，这是什么呢？
下面是普通的快速幂：
矩阵快速幂就重载一下运算符把(×)定义为矩阵乘法然后也像上面一样运算即可。
代码
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int num[1000005];
int n,s,t,e,tol;
struct map{
int a[500][500];
map operator * (const map &x) const {//重载运算符，能让矩阵乘法方便一些
//同时也符合c[i][j]=min(c[i][j],a[i][k]+b[k][j])的思路
map c;
memset(c.a,0x3f3f3f3f,sizeof(c.a));
for(int k=1;k<=tol;k++)
for(int i=1;i<=tol;i++)
for(int j=1;j<=tol;j++)
c.a[i][j]=min(c.a[i][j],a[i][k]+x.a[k][j]);
return c;
}
}dis,ans;
int main(){
memset(dis.a,0x3f3f3f3f,sizeof(dis.a));
int x,y,z;
cin>>n>>t>>s>>e;
for(int i=1;i<=t;i++){
scanf("%d %d %d",&x,&y,&z);
if(!num[y]) num[y]=++tol;
if(!num[z]) num[z]=++tol;//简便的离散化写法
dis.a[num[y]][num[z]]=dis.a[num[z]][num[y]]=x;
}
n--;
ans=dis;
while(n){//矩阵快速幂，和之前用二进制做快速幂很像，上面的运算符重载让这里很方便
if(n&1) ans=ans*dis;
dis=dis*dis;
n>>=1;
}
cout<<ans.a[num[s]][num[e]];
}
幸甚至哉，歌以咏志。