CodeForces 716D

题目

D. Complete The Graph

题面

time limit per test:4 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

ZS the Coder has drawn an undirected graph of n vertices numbered from 0 to n - 1 and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.

The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices s and t in the resulting graph is exactly L. Can you help him?

Input

The first line contains five integers n, m, L, s, t (2 ≤ n ≤ 1000,  1 ≤ m ≤ 10 000,  1 ≤ L ≤ $10^9$,  0 ≤ s, t ≤ n - 1,  s ≠ t) — the number of vertices, number of edges, the desired length of shortest path, starting vertex and ending vertex respectively.

Then, m lines describing the edges of the graph follow. i-th of them contains three integers, $u_i$,$v_i$, $w_i$(0 ≤ $u_i$, $v_i$ ≤ $n- 1$,  $u_i$ ≠ $v_i$,  0 ≤ $w_i$ ≤ $10^9$). $u_i$ and $v_i$ denote the endpoints of the edge and $w_i$ denotes its weight. If $w_i$ is equal to 0 then the weight of the corresponding edge was erased.

It is guaranteed that there is at most one edge between any pair of vertices.

Output

Print “NO” (without quotes) in the only line if it’s not possible to assign the weights in a required way.

Otherwise, print “YES” in the first line. Next m lines should contain the edges of the resulting graph, with weights assigned to edges which weights were erased. i-th of them should contain three integers $u_i$, $v_i$ and $w_i$, denoting an edge between vertices $u_i$ and $v_i$ of weight $w_i$. The edges of the new graph must coincide with the ones in the graph from the input. The weights that were not erased must remain unchanged whereas the new weights can be any positive integer not exceeding $10^{18}$.

The order of the edges in the output doesn’t matter. The length of the shortest path between s and t must be equal to L.

If there are multiple solutions, print any of them.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
input1:
5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4
input2:
2 1 123456789 0 1
0 1 0
input3:
2 1 999999999 1 0
0 1 1000000000

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
output1:
YES
0 1 5
2 1 2
3 2 3
1 4 8
4 3 4
output2:
YES
0 1 123456789
output3:
NO

note

题目大意:

给你n个点,m条边,每条边有一个正的权值,有的边权值给定,有的边权值让你自己决定(自己决定的为不超过$10^{18}$的正整数)。

同时给定距离L,要求你所决定的图从s到t的最短路距离刚好为L。

若可以,则输出YES以及任意一种方案,否则输出NO。

思路

天哪噜,这题有两个思路

P.S.虽然Dijkstra的$O({nm})$的算法可以AC,但是那是在CF,考虑到时间问题,尽量写$O({nlogn})$的Dijkstra吧~

首先考虑判断不可能的情况,无非以下几种

  1. 将所有可决定边置为INF(大于给定的L即可)之后最短路依然小于L

  2. 将所有可决定边置为1之后最短路依然大于L

特殊情况:出现刚好为L的情况,直接输出此方案即可。

下面为一般情况:(英文版及证明可见http://codeforces.com/blog/entry/47169

思路1

将所有可决定边置为1之后,跑出最短路,记录最短路上的每条边。不在最短路上的所有边置为INF。

修改已知最短路上的最后一条可修改边,使得该条路(注意此时并不一定为最短路哦~)长度刚好为L。

然后将这条修改之后的边自此不作修改,重新跑出最短路,重复以上过程。

直到某次修改以后最短路长度刚好为L,输出答案即可。

思路2

玄学算法,事先声明!

将所有可修改边编号为1~q,然后二分p

使得编号的1~p的可修改边权值为1,编号为p+1~q的可修改边权值为INF时,所求的最短路刚好dist$\leq$L

接下来我们需要做的就是在维持其它可修改边权值不变,仅仅修改p号边。

这里有一个性质,我们仅仅依次将p号边的权值从1增加到INF,那么最短路长度会由$\leq$L增长到$>$L

因此,这条边的权值长度是满足二分性质的!

那么通过二分这条边的权值,我们会得到最终的答案。

代码

代码1

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long int
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define other(x,y) ((edg[x].u==y)?(edg[x].v):(edg[x].u))
#define pii pair<LL,int>

const int maxn=1005;
const int maxm=10005;
const LL inf=1e11+7;

struct edge
{
int u,v;
LL cost;
bool f;
}edg[maxm];
priority_queue<pii,vector<pii>,greater<pii> >heap;
vector<int> g[maxn];
bool vis[maxn];
int side[maxn];
LL dis[maxn];
LL dist,tot;
int n,m;

void dij(int now,int en)
{
if(now==en)return;
vis[now]=true;
for(unsigned int i=0;i<g[now].size();i++)
{
int p=g[now][i];
int q=other(p,now);
if(vis[q])continue;
if(dis[q]>dis[now]+edg[p].cost)
{
dis[q]=dis[now]+edg[p].cost;
heap.push(make_pair(dis[q],q));
side[q]=p;
}
}
while(!heap.empty() && vis[heap.top().second])heap.pop();
if(heap.empty())return;
dij(heap.top().second,en);
}

LL Dijkstra(int st,int en)
{
while(!heap.empty())heap.pop();
memset(vis,0,sizeof(vis));
for(int i=0;i<=n;i++)dis[i]=inf+100;
dis[st]=0;
dij(st,en);
return dis[en];
}

int main()
{
bool si[maxm];
int i,j,k,st,en;
scanf("%d%d%I64d%d%d",&n,&m,&dist,&st,&en);
for(i=1;i<=m;i++)
{
scanf("%d%d%I64d",&edg[i].u,&edg[i].v,&edg[i].cost);
if(edg[i].cost==0)
{
edg[i].f=true;
edg[i].cost=inf+1;
}else edg[i].f=false;
g[edg[i].u].push_back(i);
g[edg[i].v].push_back(i);
}
tot=Dijkstra(st,en);
if(tot<dist)
{
printf("NO");
return 0;
}
if(tot==dist)
{
printf("YES\n");
for(i=1;i<=m;i++)printf("%d %d %I64d\n",edg[i].u,edg[i].v,edg[i].cost);
return 0;
}
for(i=1;i<=m;i++)if(edg[i].f)edg[i].cost=1;
tot=Dijkstra(st,en);
if(tot>dist)
{
printf("NO");
return 0;
}
printf("YES\n");
memset(si,0,sizeof(si));
j=en;
while(j!=st)
{
i=side[j];
if(edg[i].f)si[i]=true;
j=other(i,j);
}
for(i=1;i<=m;i++)
if(edg[i].f && !si[i])edg[i].cost=inf+1;
while((tot=Dijkstra(st,en))<dist)
{
j=en;
while(j!=st)
{
i=side[j];
if(edg[i].f)
{
edg[i].cost+=dist-tot;
break;
}
j=other(i,j);
}
if(j==st)break;
}
for(i=1;i<=m;i++)printf("%d %d %I64d\n",edg[i].u,edg[i].v,edg[i].cost);
return 0;
}

代码2

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long int
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define other(x,y) ((edg[x].u==y)?(edg[x].v):(edg[x].u))
#define pii pair<LL,int>

const int maxn=1005;
const int maxm=10005;
const LL inf=1e11+7;

struct edge
{
int u,v;
LL cost;
bool f;
}edg[maxm];
priority_queue<pii,vector<pii>,greater<pii> >heap;
vector<int> g[maxn];
bool vis[maxn];
int side[maxn];
LL dis[maxn];
LL dist,tot;
int n,m;

void dij(int now,int en)
{
if(now==en)return;
vis[now]=true;
for(unsigned int i=0;i<g[now].size();i++)
{
int p=g[now][i];
int q=other(p,now);
if(vis[q])continue;
if(dis[q]>dis[now]+edg[p].cost)
{
dis[q]=dis[now]+edg[p].cost;
heap.push(make_pair(dis[q],q));
side[q]=p;
}
}
while(!heap.empty() && vis[heap.top().second])heap.pop();
if(heap.empty())return;
dij(heap.top().second,en);
}

LL Dijkstra(int st,int en)
{
while(!heap.empty())heap.pop();
memset(vis,0,sizeof(vis));
for(int i=0;i<=n;i++)dis[i]=inf+100;
dis[st]=0;
dij(st,en);
return dis[en];
}

void cl(int x)
{
int temp=0;
for(int i=1;i<=m;i++)
if(edg[i].f)
{
temp++;
if(temp<=x)edg[i].cost=1;
else edg[i].cost=inf+1;
}
}

int ff(int st,int en)
{
int t=0;
for(int i=1;i<=m;i++)if(edg[i].f)t++;
int l,r,mid;
l=1;r=t;
while(r-l>1)
{
mid=(l+r)>>1;
cl(mid);
LL tot=Dijkstra(st,en);
if(tot<=dist)r=mid;else l=mid;
}
cl(l);
tot=Dijkstra(st,en);
if(tot>dist)
{
cl(l+1);
return l+1;
}else return l;
}

void find(int t,int st,int en)
{
LL l,r,mid,tot;
l=1,r=dist;
while(r-l>1)
{
mid=(l+r)>>1;
edg[t].cost=mid;
tot=Dijkstra(st,en);
if(tot==dist)return;
if(tot>dist)r=mid;else l=mid;
}
edg[t].cost=l;
tot=Dijkstra(st,en);
if(tot<dist)edg[t].cost=l+1;
}

int main()
{
int i,j,k,st,en;
scanf("%d%d%I64d%d%d",&n,&m,&dist,&st,&en);
for(i=1;i<=m;i++)
{
scanf("%d%d%I64d",&edg[i].u,&edg[i].v,&edg[i].cost);
if(edg[i].cost==0)
{
edg[i].f=true;
edg[i].cost=inf+1;
}else edg[i].f=false;
g[edg[i].u].push_back(i);
g[edg[i].v].push_back(i);
}
tot=Dijkstra(st,en);
if(tot<dist)
{
printf("NO");
return 0;
}
if(tot==dist)
{
printf("YES\n");
for(i=1;i<=m;i++)printf("%d %d %I64d\n",edg[i].u,edg[i].v,edg[i].cost);
return 0;
}
for(i=1;i<=m;i++)if(edg[i].f)edg[i].cost=1;
tot=Dijkstra(st,en);
if(tot>dist)
{
printf("NO");
return 0;
}
printf("YES\n");
int u=ff(st,en);j=0;
for(i=1;i<=m;i++)
{
if(!edg[i].f)continue;
j++;
if(j==u){k=i;break;}
}
find(k,st,en);
for(i=1;i<=m;i++)printf("%d %d %I64d\n",edg[i].u,edg[i].v,edg[i].cost);
return 0;
}

P.S.经过nike0good大佬的提醒,我们可以省去二分,在$O(1)$时间内求出P号边的权值

即正向Dijkstra以及反向Dijkstra之后,dist-dis1[u]-dis2[v]即为该条边的权值~

附核心代码

1
2
3
4
5
tot=Dijkstra(st,en);
LL p1=min(dis[edg[k].u],dis[edg[k].v]);
tot=Dijkstra(en,st);
LL p2=min(dis[edg[k].u],dis[edg[k].v]);
edg[k].cost=dist-p1-p2;