python/TangDou/AcWing/SystemOfDifferenceConstraints/P1339_BellmanFord_Ljb.cpp

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2510;          //结点数
const int M = 6200 * 2 + 10; //边数

//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

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;                              //常规的Bellman_Ford是执行n-1次
    while (T--) {                               //松驰n-1次
        for (int k = 1; k <= n; k++)            //枚举1~n节点
            for (int i = h[k]; ~i; i = ne[i]) { //二层循环枚举每个节点的出边
                int j = e[i];
                d[j] = min(d[j], d[k] + w[i]);
            }
    }
}

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);
    }
    bellman_ford(s);
    cout << d[t] << endl;
    return 0;
}