NC20684（wpy的请求 ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
const int maxm = 1e4 + 10;
struct edge{
    int v, nex; ll w;
}e[maxm];
int head[maxn], cnt, n, m;
void add_edge(int u, int v, ll w){
    e[cnt] = (edge){v, head[u], w};
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    for(int i = 0; i <= n; i++){
        head[i] = -1;
    }
}
ll val[maxn][maxn];
vector<pair<int, int>> vec;
bool vis[maxn];
ll dis[maxn];
void spfa(int s){
    for(int i = 1; i <= n; i++){
        dis[i] = 1e15;
    }
    queue<int> q;
    q.push(s); vis[s] = true; dis[s] = 0;
    while(!q.empty()){
        int u = q.front(), v; ll w; q.pop(); vis[u] = false;
        for(int i = head[u]; ~i; i = e[i].nex){
            v = e[i].v; w = e[i].w;
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                    q.push(v); vis[v] = true;
                }
            }
        }
    }
}
void print(){
    for(int i = 1; i <= n; i++){
        printf("dis[%d] = %lld\n", i, dis[i]);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    int u, v; ll w;
    for(int i =1; i <= m; i++){
        scanf("%d%d%lld", &u, &v, &w);
        add_edge(u, v, w); vec.push_back(make_pair(u, v)); val[u][v] = w;
    }
    for(int i = 1; i <= n; i++){
        add_edge(0, i, 0);
    }
    spfa(0);
    //print();
    for(auto &itm : vec){
        u = itm.first; v = itm.second;
        printf("%d %d %lld\n", u, v, dis[u] + val[u][v] - dis[v]);
    }
    return 0;
}