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; }