题目描述

“题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：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：按输入顺序输出。

题解

根据spfa的放缩原理 我们可以得知 一定是大于等于0的。

我们假设在新图上从u到v的路径权值为

假设在原图里u->v的最短路径为u->x1->x2->x3->v

那原图的最短路也就是

在我们更改了边权的新图中的最短路为：

也就是：

是一个定值,故我们更改权值之后最短路的节点顺序仍然不变。

所以我们只要把现在的边权规定为即可

代码

/*
* Coder: niiii
* Language: cpp
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+100;
const int mod=1e9+7;

struct node{
    int now,to,net,w;
}s[N];

int head[N],dis[N],in[N];
int tot=0;

void add(int u,int v,int w){
    s[++tot]={u,v,head[u],w};
    head[u]=tot;
}

void spfa(){
    queue<int> Q;
    in[0]=1;
    dis[0]=0;
    Q.push(0);
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        in[now]=0;
        for(int i=head[now];~i;i=s[i].net){
            int to=s[i].to;
            if(dis[to]>dis[now]+s[i].w){
                dis[to]=dis[now]+s[i].w;
                if(!in[to]){
                    Q.push(to);
                    in[to]=1;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    int n,m;
    memset(dis,0x3f,sizeof(dis));
    memset(head,-1,sizeof(head));
    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<<s[i].now<<" "<<s[i].to<<" "<<dis[s[i].now]-dis[s[i].to]+s[i].w<<endl;
    }
}

/*
(u,x1)+(x1,x2)+(x2,x3)+(x2,t)
*/