CF715B Complete The Graph

phmaprostrate · 2021-11-07 16:22:35 · 题解

题意

给定 n 个点 m 条边的无向图，请你修改其中边权为 0 的边，使得 s 到 t 的最短路径长为 l 其中边权范围为 1 \le w \le 10^{18}.

分析

首先，建边的顺序明显对答案没有影响，我们就可以先把边权不为 0 的边建出来，跑一遍最短路。然后，再进行分类讨论。设 d[i] 为 s 到 i 的最短路径长度。

最后要注意，开始是从 0 号点开始的，先把编号加 1 输出时再减去即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e18 + 1;
int n,m,l,s,t;
int id[N],cnt = 0;
struct node {
    int from,to,w;
} a[N];
struct ndoe {
    int to,next,w;
} tr[N];
int h[N],k = 0;
int d[N],vis[N],in[N];
queue<int> q;
void add(int from,int to,int w) {
    tr[++k].to = to;
    tr[k].next = h[from];
    tr[k].w = w;
    h[from] = k;
}
void spfa() {
    for(int i = 1 ; i <= n ; i ++) d[i] = INF,vis[i] = false,in[i] = 0;
    q.push(s),d[s] = 0,vis[s] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop(),vis[u] = false;
        for(int i = h[u] ; ~i ; i = tr[i].next) {
            int y = tr[i].to;
            if(d[y] > d[u] + tr[i].w) {
                d[y] = d[u] + tr[i].w;
                if(!vis[y]) {
                    vis[y] = true;
                    q.push(y);
                    if(++ in[y] > N) return;
                }
            }
        }
    }
}
signed main() {
    memset(h,-1,sizeof(h));
    cin >> n >> m >> l >> s >> t;
    s++,t++;
    for(int i = 1 ; i <= m ; i ++) cin >> a[i].from >> a[i].to  >> a[i].w,a[i].from++,a[i].to++;
    for(int i = 1 ; i <= m ; i ++) {
        if(a[i].w == 0) {
            id[++cnt] = i;
        } else add(a[i].from,a[i].to,a[i].w),add(a[i].to,a[i].from,a[i].w);
    }
    spfa();
    if(d[t] < l) {
        cout << "No";
        return 0;
    } else if(d[t] == l) {
        cout << "Yes"<<endl;
        for(int i = 1 ; i <= m ; i ++) {
            cout << a[i].from - 1<<" "<< a[i].to - 1<<" ";
            if(a[i].w == 0) cout << INF - 1 << endl;
            else cout << a[i].w << endl;
        }
        return 0;
    } else if(d[t] > l) {
        for(int i = 1 ; i <= cnt ; i ++) {
            a[id[i]].w = 1;
            add(a[id[i]].from,a[id[i]].to,1),add(a[id[i]].to,a[id[i]].from,1);
            spfa();
            if(d[t] > l) continue;
            if(d[t] <= l) {
                cout << "Yes"<<endl;
                a[id[i]].w =  l - d[t] + 1;
                for(int i = 1 ; i <= m ; i ++) {
                    cout << a[i].from - 1<<" " <<a[i].to - 1 <<" ";
                    if(a[i].w == 0) cout <<INF - 1 << endl;
                    else cout << a[i].w << endl;
                }
                return 0;
            }

        }
    }

    cout << "No";
    return 0;
}