You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

59 lines
1.4 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2510; //结点数
const int M = 6200 * 2 + 10; //边数
int n, m; // n个结点m条边
int s, t; //起点,终点
//邻接表
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int d[N]; //最短距离数组
bool st[N]; //是不是进过队列
// spfa模板
void spfa(int start) {
//将所有距离初始化为无穷大
memset(d, 0x3f, sizeof d);
//出发点的距离清零
d[start] = 0;
queue<int> q;
q.push(start); //出发点入队列
st[start] = true; //出发点标识已使用
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + w[i]) {
d[j] = d[t] + w[i];
if (!st[j]) {
st[j] = true;
q.push(j);
}
}
}
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
spfa(s);
cout << d[t] << endl;
return 0;
}