```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int u,v,w;
}g[105];
int n,t,s,e,m,b[205],f[105][105],ans[105][105],a[105][105];
void dbfloyd()
{
int p=n;
while(p)
{
if(p&1)
{
memset(a,0x3f,sizeof(a));
for(int k=1;k<=m;k++)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=min(a[i][j],ans[i][k]+f[k][j]);
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
ans[i][j]=a[i][j];
}
}
}
memset(a,0x3f,sizeof(a));
for(int k=1;k<=m;k++)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=min(a[i][j],f[i][k]+f[k][j]);
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=a[i][j];
}
}
p>>=1;
}
}
signed main()
{
cin>>n>>t>>s>>e;
for(int i=1;i<=t;i++)
{
cin>>g[i].w>>g[i].u>>g[i].v;
b[++m]=g[i].u;
b[++m]=g[i].v;
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=t;i++)
{
g[i]={lower_bound(b+1,b+m+1,g[i].u)-b,lower_bound(b+1,b+m+1,g[i].v)-b,g[i].w};
f[g[i].u][g[i].v]=f[g[i].v][g[i].u]=g[i].w;
}
memset(ans,0x3f,sizeof(ans));
for(int i=1;i<=m;i++) ans[i][i]=0;
dbfloyd();
cout<<ans[lower_bound(b+1,b+m+1,s)-b][lower_bound(b+1,b+m+1,e)-b];
return 0;
}
```
by Shiota_Kaede @ 2023-08-06 21:08:29
卷批。
by 沉石鱼惊旋 @ 2023-08-06 21:19:00
@[Shiota_Kaede](/user/400269) 你数组大小错了吧，设成200
by int233 @ 2023-08-06 21:34:49
@[Shiota_Kaede](/user/400269) 而且据我所知，这玩意是没有单位矩阵的吧
by int233 @ 2023-08-06 21:35:37
@[PwXmBjR_bYsVmG](/user/333855) 数组雀食开小了，另外这里 ans 雀食是这样子的，挂的地方是 f 数组的初值以及重边没处理，已经 A 了，感谢 /bx
by Shiota_Kaede @ 2023-08-06 21:46:10
卷批。
by Greenzhe @ 2023-08-11 17:06:57
@[PwXmBjR_bYsVmG](/user/333855) ?
by XHY20180718 @ 2024-02-16 11:08:04