NC20684 wpy的请求(SPFA)

题目链接

题意：




题解：

AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod = 1e9 + 7;
const int mod = 998244353;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int maxn = 1e6 + 10;
const int N = 1010;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
struct edge {
    int u, v, w, nx;
}e[maxn];
int head[maxn], cnt, n, m;
void add(int u, int v, int w) {
    e[++cnt] = {u, v, w, head[u]};
    head[u] = cnt;
}
ll dis[maxn];
bool inq[maxn];
void spfa() {
    for (int i = 0; i <= n; i++)
        dis[i] = inf, inq[i] = 0;
    queue<int> q;
    dis[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; i; i = e[i].nx) {
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) q.push(v), inq[v] = 1;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n; i++)
        add(0, i, 0);
    spfa();
    for (int i = 1; i <= m; i++)
        cout << e[i].u << ' ' << e[i].v << ' ' << dis[e[i].u] + e[i].w - dis[e[i].v] << endl;
    return 0;
}