解析：这道题本质上是求两点之间经过n条边的最短路，是一道快速幂的应用，只需把快速幂自乘的操作改成最短路边数*2，把快速幂乘答案的操作改成维护答案即可。
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
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];
bool vis[1000001];
int main()
{
memset(b,999999,sizeof(b));
memset(ans,999999,sizeof(ans));
memset(c,999999,sizeof(c));
cin>>n>>t>>s>>e;
for(int i=1;i<=t;i++)
{
cin>>z>>x>>y;
if(!vis[x])p[++num]=x,vis[x]=1,number[x]=num;
if(!vis[y])p[++num]=y,vis[y]=1,number[y]=num;
b[number[x]][number[y]]=b[number[y]][number[x]]=z;
}
for(int i=1;i<=num;i++)ans[i][i]=0;
while(n>0)
{
if(n&1)
{
memset(minn,999999,sizeof(minn));
for(int k=1;k<=num;k++)
for(int i=1;i<=num;i++)
for(int j=1;j<=num;j++)
minn[i][j]=min(minn[i][j],ans[i][k]+b[k][j]);
memcpy(ans,minn,sizeof(ans));
}
memset(c,999999,sizeof(c));
for(int k=1;k<=num;k++)
for(int i=1;i<=num;i++)
for(int j=1;j<=num;j++)
c[i][j]=min(c[i][j],b[i][k]+b[k][j]);
memcpy(b,c,sizeof(b));
n>>=1;
}
cout<<ans[number[s]][number[e]];
return 0;
}