40 lines
834 B
C++
40 lines
834 B
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
const int N = 2510; //结点数
|
||
const int M = 6200 * 2 + 10; //边数
|
||
|
||
struct Edge {
|
||
int a, b, c;
|
||
} edges[M];
|
||
|
||
int n, m; // n个结点，m条边
|
||
int s, t; //起点，终点
|
||
int d[N]; //距离数组
|
||
|
||
void bellman_ford(int start) {
|
||
memset(d, 0x3f, sizeof d);
|
||
d[start] = 0;
|
||
int T = n - 1;
|
||
while (T--) {
|
||
for (int i = 0; i < 2 * m; i++) {
|
||
auto j = edges[i];
|
||
d[j.b] = min(d[j.b], d[j.a] + j.c);
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
cin >> n >> m >> s >> t;
|
||
for (int i = 0; i < m; i++) {
|
||
int a, b, c;
|
||
cin >> a >> b >> c;
|
||
edges[i] = {a, b, c}, edges[m + i] = {b, a, c};
|
||
}
|
||
bellman_ford(s);
|
||
|
||
cout << d[t] << endl;
|
||
return 0;
|
||
}
|