来源：牛客网：
@[toc]

wpy的请求

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

“题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：o(￣▽￣)o” —— 历史——殿堂

wpy移情别恋啦，他不喜欢spfa了，现在他喜欢使用dij，但是他又发现了一个新的问题，dij无法跑有负权边的图，于是wpy找到了她的男朋友也就是你来帮忙，为了你晚上的幸福生活，你必须在1秒内帮她解决这个问题，然后蹿到床上。。。balabala（捂脸）。。。。(/ω＼)
简单来说，有一张n个点，m条边的有向图，请你给每条边确定一个新的边权（不同边之间可以不同），保证对于任意u，v，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不变。
新的边权要求非负。

输入描述:

第一行两个整数n,m,表示有n个点，m条边。

接下来m行，每行三个数，u，v，w，表示有一条从u到v。

输出描述:

输出m行，每行三个整数u,v,w表示有从u到v的边边权改完后是为w。

ps：按输入顺序输出。
示例1
输入
复制

5 10
1 2 -4383
1 3 -9930
2 4 -7331
1 5 -2175
2 3 11962
2 5 16382
4 5 11420
1 4 37978
3 5 13836
3 4 14617

输出
复制

1 2 0
1 3 0
2 4 0
1 5 0
2 3 17509
2 5 14174
4 5 1881
1 4 49692
3 5 6081
3 4 16401

备注:

n<=103，m<=3*103，|w|<=109 数据保证有解，保证没有负环，保证任意两点间最短路唯一,保证图联通 数据有梯度（
但是出题人也不知道能写什么部分分）

题解：

所有边加相同值变正肯定不行，具体看官方题解第一段
其实想明白就不难
先说结论：建立一个超级源点与每个节点相连，边权为0，然后从超级源点跑spfa，对于u到v边权为w的边，新边权为dis[u]-dis[v]+w
原理：
spfa中更新最短路径的关键是：dis[v]>=dis[u]+w
当满足这个条件时，路径就可以更新。而当路径为最短路时，也就有dis[u]+w-dis[v]>=0成立
我们再看看点u到v的最短路径为u->x->y->v
那么最短路径长度就是：dis（u，x）+dis（x，y）+dis（y，v）
dis（u，x）表示u到x的最短路径
现在我们要更改边权，（因为边权值可能为负数），使得单个边权的值>=0，
dis[u]+w-dis[v]>=0,w就相当于dis（u，x）,我们带入得到：
dis[u]-dis[x]+dis[x]-dis[y]+dis[y]-dis[v]+dis（u，x）+dis（x，y）+dis（y，v）
化简得：
dis（u，x）+dis（x，y）+dis（y，v）+dis[u]-dis[v]
dis[u]-dis[v]是定值
前面三个就是原路径的w，这不就是我们一开始说的结论

代码：

#include <bits/stdc++.h> 
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct node
{
    int to,next,w,u;
}edge[100005];
long long 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()){
        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;
}