#include <bits/stdc++.h>
#define maxn 2505
using namespace std;
int a[maxn][maxn];
int n, m, s, t;
int in_queue[maxn];
queue<int> q;
int relax(int u, int v)
{
if (a[s][u] + a[u][v] < a[s][v])
{
a[s][v] = (a[s][u] + a[u][v]);
return 1;
}
return 0;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i(1); i <= n; ++i)
for (int j(1); j <= n; ++j)
a[i][j] = 114514;
while (m--)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
a[u][v] = w;
a[v][u] = w;
}
q.push(s);
in_queue[s] = true;
while (!q.empty())
{
int u = q.front();
q.pop();
in_queue[u] = false;
for (int i(1); i <= n; ++i)
if (relax(u, i) && !in_queue[i])
{
q.push(i);
in_queue[i] = true;
}
}
printf("%d\n", a[s][t]);
return 0;
}
// SPFA 70 pts ???????
Floyd O(n3) 能跑 80pts 但是为什么 SPFA 最坏情况 O(nm) 只能跑到 70pts /kk
1≤n≤2500 1≤m≤6200