wpy的请求 （spfa变形求负权通路）

wpy的请求 spfa变形

题目大意：给一个n个点，m条边的有向图，可能有负权边，现在要把负边权都变成非负，
并且使得原图中的任意两点u,v最短路经过路径不变并且使得原图中的任意两点u,v最短路经过路径不变

解题思路：解法就是建立一个超级原点（也就是0节点），与所有点相连，且边权值为0，然后跑一遍spfa，然后边权答案就是 dis[u]-dis[v]+w。

这是因为spfa的松弛操作的条件是 dis[v]>dis[u]+w 所以松弛后 dis[u]-dis[v]+w>=0 是一定成立的，
所以边权都为非负了。

Code：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int ll;
const int maxn=1e6+10;

ll dis[maxn];
bool vis[maxn];

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

void spfa(){
    for(int i=0;i<=n;i++) dis[i]=inf,vis[i]=0;

    queue<int> q;
    dis[0]=0; q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        vis[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(!vis[v]) q.push(v),vis[v]=1;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    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]-dis[e[i].v]+e[i].w<<"\n";
    }
    return 0;
}