#include <bits/stdc++.h>
#define N 25001
#define M 62001
using namespace std;
struct Edge {
int x, y, z, next;
Edge(int x = 0, int y = 0, int z = 0, int next = 0) :
x(x), y(y), z(z), next(next) {}
} edge[M * 2];
int n, m, s, t, sumedge, head[N];
bool vis[N];
int inn[N], dis[N];
void ins(int x, int y, int z) {
edge[++sumedge] = Edge(x, y, z, head[x]);
head[x] = sumedge;
return;
}
bool SPFA(int x) {
queue<int> q;
memset(dis, 0x3f, sizeof dis);
memset(vis, false, sizeof vis);
memset(inn, 0, sizeof inn);
dis[x] = 0;
q.push(x);
vis[x] = 1;
inn[x] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
vis[t] = 0;
for (int u = head[t]; u; u = edge[u].next) {
int temp = edge[u].y;
if (dis[temp] > dis[t] + edge[u].z) {
dis[temp] = dis[t] + edge[u].z;
if (!vis[temp]) {
vis[temp] = 1;
inn[temp]++;
q.push(temp);
if (inn[temp] > n) return false;
}
}
}
}
return true;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
ins(x, y, z);
ins(y, x, z);
}
if (SPFA(s)) printf("%d", dis[t]);
return 0;
}
网友评论