wpy的请求

题目地址：

https://ac.nowcoder.com/acm/problem/20684

基本思路：

参考了官方出题人的题解。
这题实际做法比较简单，但是可能比较难以想到。
做法就是我们找一个超级源点和每个节点连一条权值为的边,然后我们再从这个超级源点出发跑一个,然后对于到权值为的边，就是我们应该设定的新权值。
接下来我们来证明这样为什么是对的：
首先根据最短路的放缩原理 即 成立。
然后我们再看为什么在新图上最短路径不会改变：
假设原图里的最短路径为
最短路也就是
然后我们更改了边权最短路变为：
然后化简一下就变为：
多出来了一个 这是一个定值，所以只要在原图里是最短路径，在新图里也会同样是最短路径。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}


const int maxn = (int)1e3 + 10;

int n,m;

class Graph {

private:

    int cnt = 0, head[maxn];

    struct Edge {
        int next, to, w;
    } edge[maxn * 4];

public:

    void init() {
      cnt = 0;
      memset(head, -1, sizeof(head));
    }

    void add_edge(int u, int v, int w) {
      edge[++cnt] = {head[u], v, w};
      head[u] = cnt;
    }

    bool vis[maxn];
    int dis[maxn], count[maxn];

    bool spfa(int k) {
      for (int i = 0; i <= n; i++)
        vis[i] = false, dis[i] = INF, count[i] = 0;
      queue<int> q;
      dis[k] = 0;
      vis[k] = true;
      q.push(k);
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i != -1; i = edge[i].next) {
          int to = edge[i].to;
          if (dis[to] > dis[u] + edge[i].w) {
            dis[to] = dis[u] + edge[i].w;
            if (!vis[to]) {
              vis[to] = true;
              q.push(to);
              count[to]++;
              if (count[to] >= n) return true;
            }
          }
        }
      }
      return false;
    }

}G;
vector<vector<int>> memo;
signed main() {
  IO;
  G.init();
  n = read(),m = read();
  rep(i,1,n) G.add_edge(0,i,0);
  rep(i,1,m) {
    int u = read(), v = read(), w = read();
    G.add_edge(u, v, w);
    memo.push_back({u,v,w});
  }
  G.spfa(0);
  for(auto it : memo){
    int u = it[0],v = it[1] ,w = it[2];
    int res = G.dis[u] - G.dis[v] + w;
    cout << u << ' ' << v << ' ' << res << '\n';
  }
  return 0;
}