Codeforces 716D(最短路+枚举加边)

Codeforces 716D
题意:$n$个点$0~n-1$和$m$条边的无向图,每条边上有一个正权或0,0可以改成任何正权,求一个方案使得$s$到$t$最短路为$L$.
解:考虑将 0 边先全部删除,然后再进行添加。
先对原图进行一次最短路,如果此时$s$到$t$最短路小于$L$,显然无解,如果等于则直接输出
否则我们开始随意加边,加最小正边权为$1$,注意正边权。然后每次加完边以后做最短路,如果当前最短路小于$L$,则可以直接输出了,但是这条边要改成适当的权来使最短路变为$L$。

1、枚举最短路要考虑2/4种情况
2、要挖掘题目中所有的限制
3、要严格按照做题步骤去想,先写题意,再想题目类型,五大思维方式

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 1000 + 5, MAXM = 10000 + 5;
struct edge {int u, v, w, nxt;} ed[MAXM * 2];
struct zoe {int s, t;} whw[MAXM];
struct data {
int u;
LL dis;
bool operator < (const data &b) const {return dis > b.dis;}
};
priority_queue<data > q;
int n, m, L, s, t, en, orz, hd[MAXN], cnt;
int vis[MAXN];
LL dis[MAXN];
void ins(int x, int y, int w) {ed[++en] = (edge){x, y, w, hd[x]}, hd[x] = en;}
void dij(int ss) {
for (int i = 0; i <= n; ++i) vis[i] = 0, dis[i] = LLONG_MAX / 2;
dis[ss] = 0, q.push((data){ss, 0});
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue;
vis[p.u] = true;
for (int i = hd[p.u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (dis[e.v] > dis[p.u] + e.w) {
dis[e.v] = dis[p.u] + e.w;
q.push((data){e.v, dis[e.v]});
}
}
}
}
void pri(int hh) {
printf("YES\n");
for (int i = 1; i <= orz; i += 2) printf("%d %d %d\n", ed[i].u, ed[i].v, ed[i].w);
for (int i = 1; i < hh; ++i) printf("%d %d %d\n", whw[i].s, whw[i].t, 1);
dij(s);
LL tmp1 = dis[whw[hh].s], tmp2 = dis[whw[hh].t];
dij(t);
tmp1 += dis[whw[hh].t], tmp2 += dis[whw[hh].s];
if (hh >= 1) printf("%d %d %lld\n", whw[hh].s, whw[hh].t, L - min(tmp1, tmp2));
for (int i = hh + 1; i <= cnt; ++i) printf("%d %d %lld\n", whw[i].s, whw[i].t, 10000000000ll);
}
void clean() {
orz = cnt = en = 0, ms(hd, -1);
}
int solve() {
cin >> n >> m >> L >> s >> t;
clean();
for (int x, y, w, i = 1; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &w);
if (w != 0) ins(x, y, w), ins(y, x, w);
else whw[++cnt] = (zoe){x, y};
}
orz = en;
dij(s);
if (dis[t] < L) return printf("NO\n"), 0;
if (dis[t] == L) return pri(0), 0;
int gg = 0;
for (int i = 1; i <= cnt; ++i) {
ins(whw[i].s, whw[i].t, 1), ins(whw[i].t, whw[i].s, 1);
dij(s);
if (dis[t] <= L) {gg = i; break ;}
}
if (dis[t] <= L) pri(gg); else printf("NO\n");
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------