首页 > 编程学习 > 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
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,然后对于uv权值为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
*/

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

 

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号