wpy的请求

要把一个带负边权的图改为非负的，并且还要最短路的路径不变
可以利用spfa的缩放
因为dis[v] > dis[u]+w 所以dis[u]-dis[v]+w > 0
用一个节点作为超级源节点，与每一个的距离都是0，然后spfa进行缩放

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#define ll long long
#define pi 3.1415927
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;
#define _int __int128_t
int n,m;
struct node
{
    int to,next,w,u;
    /* data */
}edge[100005];
ll head[10005],tot=0,vis[10005],dis[10005];
void add(int u,int v, int w)
{
    edge[++tot].to=v;
    edge[tot].w=w;
    edge[tot].u=u;
    edge[tot].next=head[u];
    head[u]=tot;
}
void spfa()
{
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    while(!q.empty()){
        //cout<<"!";
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u]; i ;i=edge[i].next){
            int v=edge[i].to,w=edge[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
                }
            }
        }
    }
}
int main ()
{
    int T,i,t,j,k,p,sum=0,v,u,w;
    cin>>n>>m;
    for(i=0;i<m;++i){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    for(i=1;i<=n;++i)
        add(0,i,0);
    spfa();
    for(i=1;i<=m;++i){
        u=edge[i].u; v=edge[i].to; w=edge[i].w;
        printf("%d %d %d\n",u,v,dis[u]-dis[v]+w);
    }

    return 0;
}