1034 wpy的请求 保证最短路径不变 将负权图改成正权图

 链接：https://ac.nowcoder.com/acm/contest/26077/1034
来源：牛客网

题目描述

“题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：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<br />1 2 -4383<br />1 3 -9930<br />2 4 -7331<br />1 5 -2175<br />2 3 11962<br />2 5 16382<br />4 5 11420<br />1 4 37978<br />3 5 13836<br />3 4 14617

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<br />1 3 0<br />2 4 0<br />1 5 0<br />2 3 17509<br />2 5 14174<br />4 5 1881<br />1 4 49692<br />3 5 6081<br />3 4 16401

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

分析

题意：保持最短路的顺序不变，将所有边的边权边成正值。

做法就是我们找一个超级源点和每个节点连一条权值为0的边,然后我们再从这个超级源点出发跑一个spfa,然后对于u到v权值为w的边，dis[u] – dis[v] + w就是我们应该设定的新权值。

ps:这个起始点无论是哪个点都可以，我们只需要求出 到每个节点的最短路，最后都会被约掉（换言之，将所有边权变成正边权有多种可能）。

对于最短路，松弛：dist[v] > dist[u] + w;

所以在松弛之后总是满足 dist[u] – dist[v] + w >= 0。用这个距离替换 w(u,v)

原本的u到v 的最短路：w(u,x1) + w(x1,x2) + w(x2,v);

替换后：dis[u] – dis[x1] + w(u,x1) + dis(x1) – dis(x2) + w(x1,x2) + dis(x2) – dis(v) + w(x2,v)

化简：w(u,x1) + w(x1,x2) + w(x2,v) + dis(u) – dis(v) 由于dis(u) – dis(v)是常数，对最短路不会有影响，所以合法

//-------------------------代码----------------------------

//#define int ll
const int N = 1e5+10;
int n,m;
int e[N],ne[N],w[N],h[N],idx;
int dist[N];
bool vis[N];

void add(int a,int b,int c) {
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;
}

void spfa() {
    priority_queue<pii,V<pii>,greater<pii>> q;
    ms(dist,0x3f)
    q.push({0,0});
    dist[0] = 0;
    while(q.size()) {
        auto t = q.top();q.pop();
        int ver = t.y;
        vis[ver] = 0;
        fe(i,ver) {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                if(!vis[j]) {
                    q.push({dist[j],j});
                    vis[j] = 1;
                }
            }
        }
    }
}

void solve()
{
    cin>>n>>m;
    ms(h,-1);
    fo(i,1,n) add(0,i,0);
    V<V<int>> qq;
    fo(i,1,m) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        qq.push_back({a,b,c});
    }
    spfa();
    for(auto it:qq) {
        int a = it[0],b = it[1],c = it[2];
        int res = dist[a] - dist[b] + c;
        cout<<a<<' '<<b<<' '<<res<<endl;
    }
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区
1
2 3
2 4
1 5
1 6
1 2
*/

//------------------------------------------------------------