题意很简单，给一张图，把基本的求起点到终点最短路改成求经过k条边的最短路。
求最短路常用的算法是dijkstra，SPFA，还有floyd。
考虑floyd的过程：
c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
自然而然联想到矩阵乘法，每次加入一个点就相当于多加一条边，那么加k次就是k条边的最短路。
但是k可能很大（见数据范围），那么显然直接循环矩乘k次是行不通的，于是就想到了矩阵快速幂。
和普通快速幂一样的方式，只不过是把乘法替换成矩乘。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int n,t,s,e,num;
int p[];
struct M{
long long v[][];
};
M gra,ans;
M cheng(M a,M b){
M kk;
memset(kk.v,0x3f,sizeof(kk.v));
for(int k=;k<=num;k++){
for(int i=;i<=num;i++){
for(int j=;j<=num;j++){
kk.v[i][j]=min(kk.v[i][j],a.v[i][k]+b.v[k][j]);
}
}
}
return kk;
}
void ks(int x){
while(x){
if(x&){
ans=cheng(gra,ans);
}
gra=cheng(gra,gra);
x>>=;
}
}
int main()
{
scanf("%d%d%d%d",&n,&t,&s,&e);
memset(gra.v,0x3f,sizeof(gra.v));
memset(ans.v,0x3f,sizeof(ans.v));
for(int i=;i<=t;i++){
int a,b;
long long c;
scanf("%lld%d%d",&c,&a,&b);
if(!p[a])p[a]=++num;
if(!p[b])p[b]=++num;
gra.v[p[a]][p[b]]=gra.v[p[b]][p[a]]=min(gra.v[p[b]][p[a]],c);
}
for(int i=;i<=num;i++)ans.v[i][i]=;
ks(n);
printf("%lld",ans.v[p[s]][p[e]]);
return ;
}