C++ 代码
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
const int N=1010;
int g[N][N];
int res[N][N];
int k,t,s,e,n;
map<int,int> ids;
void mul(int c[][N],int a[][N],int b[][N]){
static int t[N][N];
memset(t,0x3f,sizeof t);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
t[i][j]=min(t[i][j],a[i][k]+b[k][j]);
memcpy(c,t,sizeof t);
}
void qmi(){
memset(res,0x3f,sizeof res);
for(int i=1;i<=n;i++) res[i][i]=0;
while(k){
if(k&1) mul(res,res,g);
mul(g,g,g);
k>>=1;
}
}
int main(){
cin>>k>>t>>s>>e;
memset(g,0x3f,sizeof g);
if(!ids.count(s)) ids[s]=++n;
if(!ids.count(e)) ids[e]=++n;
s=ids[s];
e=ids[e];
for(int i=0;i<t;i++){
int a,b,w;
cin>>w>>a>>b;
if(!ids.count(a)) ids[a]=++n;
if(!ids.count(b)) ids[b]=++n;
a=ids[a]; b=ids[b];
g[a][b]=g[b][a]=min(g[a][b],w);
}
qmi();
cout<<res[s][e]<<endl;
return 0;
}