大概是叫倍增Floyd？
显然最多200个点...f[i][j][k]表示从j到k，走2^i步的最小路程。就随便转移了。。
查询的话就是把n二进制位上是1的那些都并起来。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define ll long long
#define ull unsigned long long
#define d double
using namespace std;
const int maxn=,inf=;
struct mat{int f[][];}f,c;
int id[];
int i,j,k,n,m,cnt,st,ed; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
inline int min(int a,int b){return a<b?a:b;}
inline mat run(mat &a,mat &b){
register int i,j,k;
for(i=;i<=cnt;i++)for(j=;j<=cnt;j++)
for(c.f[i][j]=inf,k=;k<=cnt;k++)
c.f[i][j]=min(c.f[i][j],a.f[i][k]+b.f[k][j]);
return c;
}
int main(){
n=read(),m=read(),st=read(),ed=read();int x;
memset(f.f,,sizeof(f.f));
for(i=;i<=m;i++){
x=read(),j=read(),k=read();
if(!id[j])id[j]=++cnt;if(!id[k])id[k]=++cnt;
j=id[j],k=id[k];
f.f[j][k]=min(f.f[j][k],x),f.f[k][j]=min(f.f[k][j],x);
}
mat g=f;n--;
while(n){
if(n&)g=run(g,f);
n>>=;
if(n)f=run(f,f);
}
printf("%d\n",g.f[id[st]][id[ed]]);
}