算法板子

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int he[N], w[N], e[N], ne[N];
int idx, n, m;
int d[N];
bool st[N];
queue<int> q;
void add(int x, int y, int z) {
    w[idx] = z;
    e[idx] = y;
    ne[idx] = he[x];
    he[x] = idx++;
}
int spfa() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    st[1] = true;
    q.push(1);
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = he[t]; i != -1; 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);
                }
            }
        }
    }
    if (d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}
int main() {
    memset(he, -1, sizeof he);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    int r = spfa();
    if (r == -1) cout << "impossible" << endl;
    else cout << r << endl;
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/find-the-shortest-path-with-spfa/
最后修改日期:2020年6月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。