CF-715B Complete The Graph

题意

给 n,(2≤n≤1000)n,(2\le n\le 1000) 点 m,(1≤m≤10000)m,(1\le m\le 10000) 边的无向图，修改 mm 条边中边为 00 的边，使满足 s,t,(0≤s,t,ui,vi≤n−1,s≠t,0≤wi≤109)s,t,(0\le s,t,u_i,v_i\le n-1,s\ne t,0\le w_i\le 10^9) 的最短路长度是 L,(0≤L≤109)L,(0\le L \le 10^9) ，且输出答案的时候边为 00 的边的权值必须在 [1,1018][1,10^{18}] 内。

题解

把所有为零的边赋为 11 跑一遍最短路，用 disdis 表示，显然若 dist>Ldis_t > L 输出无解。

然后我们有一个naive的想法，给那些可修改的边依次 +1+1，（可以修改的边权为 w1,w2,…,wew_1,w_2,\dots,w_e，我们的“操作序列”便是 w1=2,w2=2,…,we=2,w1=3,w2=3,…,we=3,…we=Lw_1=2,w_2=2,\dots,w_e=2,w_1=3,w_2=3,\dots,w_e=3,\dots w_e=L），操作序列的长度为 e(L−1)e(L-1) ，ee 为可修改的边数。显然如果执行完“操作序列”，dist′<Ldis_t'\lt L 肯定无解，不然在某次修改后 dist′=Ldis_t'=L ，因为一次修改最多让 dist′dis_t' 增加 11

二分操作序列，每次跑一遍 Dijkstra ，复杂度 O(nlog⁡nlog⁡(ml))O(n\log n\log(ml)) ，能过，但有更优秀的做法。

考虑在第一次 Dijkstra （可修改的边权赋 11）后处理出 disidis_i ，记 dif=L−distdif=L-dis_t ，dif<0dif<0 无解。 再跑一遍 Dijkstra ，dis′dis' 为新的距离，此时对于任意一条边 (u,v)(u,v) 若 disu′+wu→v<disv+difdis_u'+w_{u\to v} \lt dis_v+dif 修改边权 wu→v′=disv+dif−disu′w_{u\to v}' = dis_v+dif-dis_u' ，若最后 dist≠Ldis_t\ne L 则无解。

考虑这样做为毛是对的，根据上面naive的想法，若所有边都赋最大值最短路还比 LL 小就无解，不然一定有解。

我们的修改保证了 disu′+wu→v′≥disv+difdis_u'+w_{u\to v}'\ge dis_v+dif ，故可以保证 dist′≥Ldis_t'\ge L 。再考虑一定存在一条最短的路径满足 disu′+wu→v′=disv+dif=disv′dis_u'+w_{u\to v}'= dis_v+dif=dis_v' ，故 dist′=Ldis_t'=L 。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define inf (L+100)
using namespace std;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
const int N = 1005;
const int M = 10005;
typedef long long ll;
typedef pair<int,int> pii;
int head[N],nxt[M<<1],pnt[M<<1],wth[M<<1],E=-1;
int n,m,s,t,L,dif;
bool can[M<<1];
ll ds[2][N];
vector<int> e;
bool vis[N];
void adde(int u,int v,int w) {
    E++;pnt[E]=v;nxt[E]=head[u];wth[E]=w;head[u]=E;
    if(w==0) e.push_back(E),can[E]=1;
}
void dij(bool fg) {
    memset(ds[fg],0x3f,sizeof(ds[fg]));
    ds[fg][s]=0;
    memset(vis,0,sizeof(vis));
    priority_queue<pii> q;q.push(pii(0,s));
    while(!q.empty()) {
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=nxt[i]) {
            int v=pnt[i];
            if(fg&&can[i]) {
                if(ds[1][u]+wth[i]<ds[0][v]+dif) wth[i]=wth[i^1]=ds[0][v]+dif-ds[1][u];              
            }
            if(ds[fg][u]+wth[i]<ds[fg][v]) {
                ds[fg][v]=ds[fg][u]+wth[i];
                q.push(pii(-ds[fg][v],v));
            }
        }
    }
}
int main() {
    red(n);red(m);red(L);red(s);red(t);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++) {
        int u,v,w;
        red(u);red(v);red(w);
        adde(u,v,w);adde(v,u,w);
    }
    for(auto i:e) wth[i]=1;
    dij(0);
    if(ds[0][t]>L) {puts("NO");return 0;} 
    dif=L-ds[0][t];
    dij(1);
    if(ds[1][t]!=L) {puts("NO");return 0;} 
    puts("YES");
    for(int i=0;i<=E;i+=2) {
        printf("%d %d %d\n",pnt[i^1],pnt[i],wth[i]);
    }
    return 0;
}