链接
https://codeforces.com/contest/716/problem/D
题意
无向图中，给权值可变边赋值，使最短路为 $L$。
思路一
忽略可变边，若最短路 $<L$，无解。
将可变边全部赋值为 $1$，若最短路 $>L$，无解。
否则，有解。
设当前最短路径为 $A$，将 $A$ 上的一条可变边增大到使 $A$ 上边权和为 $L$，其余不在 $A$ 上的可变边赋值为 $>=L$ 的值。
这次操作中修改过的边都打上标记，那么还剩下 $A$ 中其余为 $1$ 的可变边。
再次跑最短路，如果最短路 $\neq L$，将最短路径上的一条未标记的可变边增大到使最短路为 $L$，并给这条边打上标记。
总共最多会跑 $n$ 次最短路。
时间复杂度：$O(nm\log(m))$
代码一
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int N=1e3+5;
const int M=1e4+5;
int n,m,s,t,a[M],b[M],pre[N],id[N][N],path[N];
LL L,c[M],dist[N];
bool f[M],ff[M],st[N];
VPII g[N];
VI e;
struct R {
LL w;
int u;
R() {}
R(LL w,int u):w(w),u(u) {}
bool operator < (const R &T) const {
return w>T.w;
}
};
LL dijkstra() {
for(int i=1;i<=n;i++) {
dist[i]=INF;
st[i]=false;
}
priority_queue<R> q;
q.emplace(0,s);
dist[s]=0;
while(SZ(q)) {
int u=q.top().u;
q.pop();
if(st[u]) continue;
st[u]=true;
for(auto x:g[u]) {
int v=x.FI;
LL w=c[x.SE];
if(!st[v]&&dist[u]+w<dist[v]) {
dist[v]=dist[u]+w;
pre[v]=u;
if(f[x.SE]) path[v]=x.SE;
else path[v]=path[u];
q.emplace(dist[v],v);
}
}
}
return dist[t];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>L>>s>>t;
++s,++t;
for(int i=1;i<=m;i++) {
cin>>a[i]>>b[i]>>c[i];
++a[i],++b[i];
id[a[i]][b[i]]=id[b[i]][a[i]]=i;
if(c[i]) {
g[a[i]].EB(b[i],i);
g[b[i]].EB(a[i],i);
}
else f[i]=true,e.PB(i);
}
if(dijkstra()<L) return cout<<"NO"<<'\n',0;
for(auto x:e) {
c[x]=1;
g[a[x]].EB(b[x],x);
g[b[x]].EB(a[x],x);
}
if(dijkstra()>L) return cout<<"NO"<<'\n',0;
int tt=0;
for(int u=pre[t],v=t;u;v=u,u=pre[u]) if(f[id[u][v]]) {
ff[id[u][v]]=true;
c[id[u][v]]=1;
tt=id[u][v];
}
c[tt]=L-dist[t]+c[tt];
for(auto x:e) if(!ff[x]) {
f[x]=false;
c[x]=1e10;
}
while(dijkstra()!=L) {
f[path[t]]=false;
c[path[t]]=L-dist[t]+c[path[t]];
}
cout<<"YES"<<'\n';
for(int i=1;i<=m;i++) cout<<a[i]-1<<' '<<b[i]-1<<' '<<c[i]<<'\n';
return 0;
}
|
思路二
设可变边集合为 $e$，每条边初始值为 $0$，考虑依次给每条可变边 $+1$
即：$e_1+1,e_2+1,e_3+1,\dots,e_k+1,e_1+1,e_2+1,\dots$
每次最短路最多 $+1$
二分 $+1$ 次数跑 dijkstra
时间复杂度：$O(\log(mL)m\log(m))$
代码二
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int N=1e3+5;
const int M=1e4+5;
int n,m,s,t,a[M],b[M];
LL L,c[M],dist[N];
bool st[N];
VPII g[N];
VI e;
struct R {
LL w;
int u;
R() {}
R(LL w,int u):w(w),u(u) {}
bool operator < (const R &T) const {
return w>T.w;
}
};
LL dijkstra() {
for(int i=1;i<=n;i++) {
dist[i]=INF;
st[i]=false;
}
priority_queue<R> q;
q.emplace(0,s);
dist[s]=0;
while(SZ(q)) {
int u=q.top().u;
q.pop();
if(st[u]) continue;
st[u]=true;
for(auto x:g[u]) {
int v=x.FI;
LL w=c[x.SE];
if(!st[v]&&dist[u]+w<dist[v]) {
dist[v]=dist[u]+w;
q.emplace(dist[v],v);
}
}
}
return dist[t];
}
LL check(LL mid) {
for(auto x:e) c[x]=mid/m+(x<=mid%m);
return dijkstra();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>L>>s>>t;
++s,++t;
for(int i=1;i<=m;i++) {
cin>>a[i]>>b[i]>>c[i];
++a[i],++b[i];
g[a[i]].EB(b[i],i);
g[b[i]].EB(a[i],i);
if(!c[i]) e.PB(i);
}
LL l=m,r=L*m+1;
while(l<=r) {
LL mid=l+r>>1;
LL ret=check(mid);
if(ret==L) {
cout<<"YES"<<'\n';
for(int i=1;i<=m;i++) cout<<a[i]-1<<' '<<b[i]-1<<' '<<c[i]<<'\n';
return 0;
}
else if(ret>L) r=mid-1;
else l=mid+1;
}
cout<<"NO"<<'\n';
return 0;
}
|
思路三
将可变边全部赋值为 $1$，若最短路 $>L$，无解。
记第一次跑最短路时从起点到 $i$ 的最短路为 $dist_{i,0}$，$diff=L-dist_{t,0}$。
再次跑最短路，记为 $dist_{i,1}$，对于每一条可变边 $x\rightarrow y$，如果 $dist_{x,1}+w<dist_{y,0}+diff$，那么将该边边权修改为 $dist_{y,0}+diff-dist_{x,1}$。
最后判断 $dist_{t,1}$ 是否 $=L$。
解释：
第一次跑完最短路后，我们求出了需要给最短路增加 $diff$ 才能满足题目要求，
如果我们随意找一条最短路径上的可变边增加 $diff$，那么当前路径虽然值为 $L$，但不一定最短。
所以我们让存在可变边的路径都增加 $diff$，那么最终最短路一定为 $L$，除非存在一条比 $L$ 小且没有可变边的路径。
时间复杂度：$O(m\log(m))$
代码三
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int N=1e3+5;
const int M=1e4+5;
int n,m,s,t,a[M],b[M];
LL L,c[M],dist[N][2];
bool st[N],f[M];
VPII g[N];
struct R {
LL w;
int u;
R() {}
R(LL w,int u):w(w),u(u) {}
bool operator < (const R &T) const {
return w>T.w;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>L>>s>>t;
++s,++t;
for(int i=1;i<=m;i++) {
cin>>a[i]>>b[i]>>c[i];
++a[i],++b[i];
g[a[i]].EB(b[i],i);
g[b[i]].EB(a[i],i);
if(!c[i]) c[i]=1,f[i]=true;
}
for(int i=1;i<=n;i++) dist[i][0]=dist[i][1]=INF;
priority_queue<R> q;
q.emplace(0,s);
dist[s][0]=dist[s][1]=0;
while(SZ(q)) {
int u=q.top().u;
q.pop();
if(st[u]) continue;
st[u]=true;
for(auto x:g[u]) {
int v=x.FI;
LL w=c[x.SE];
if(!st[v]&&dist[u][0]+w<dist[v][0]) {
dist[v][0]=dist[u][0]+w;
q.emplace(dist[v][0],v);
}
}
}
LL diff=L-dist[t][0];
if(diff<0) return cout<<"NO"<<'\n',0;
for(int i=1;i<=n;i++) st[i]=false;
q.emplace(0,s);
while(SZ(q)) {
int u=q.top().u;
q.pop();
if(st[u]) continue;
st[u]=true;
for(auto x:g[u]) {
int v=x.FI;
LL &w=c[x.SE];
if(f[x.SE]) {
if(dist[u][1]+w<dist[v][0]+diff) w=dist[v][0]+diff-dist[u][1];
}
if(!st[v]&&dist[u][1]+w<dist[v][1]) {
dist[v][1]=dist[u][1]+w;
q.emplace(dist[v][1],v);
}
}
}
if(dist[t][1]==L) {
cout<<"YES"<<'\n';
for(int i=1;i<=m;i++) cout<<a[i]-1<<' '<<b[i]-1<<' '<<c[i]<<'\n';
}
else cout<<"NO"<<'\n';
return 0;
}
|