UVA10806 Dijkstra, Dijkstra.

题目链接

题意

求一条 $s$ 到 $t$ 的最短往返路,要求不能走重复的边。

分析

考虑网络流中的退流操作。

先跑一遍s到t的最短路,然后把这条路的权值都更新为正无穷,保证之后不会再走第二遍。然后把相应地反向边的权值变成相反数。

再跑一次s到t的最短路,此时如果走到之前的反向边,则相当于“退流”。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int G[maxn][maxn];
int p[maxn], d[maxn];
int n, m;

void dijsktra(int s, int t) {
for (int i = 1; i <= n; i++) d[i] = INF;
d[s] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(make_pair(0, s));
while (!pq.empty()) {
pii now = pq.top();
pq.pop();
int v = now.second;
if (d[v] < now.first) continue;
for (int i = 1; i <= n; i++) {
if (G[v][i] < INF) {
if (d[i] > d[v] + G[v][i]) {
d[i] = d[v] + G[v][i];
p[i] = v;
pq.push({d[i], i});
}
}
}
}
}

int main() {
while (~scanf("%d", &n)) {
if (!n) break;
memset(G, 0x3f, sizeof(G));
scanf("%d", &m);
for (int i = 0, u, v, t; i < m; i++) {
scanf("%d%d%d", &u, &v, &t);
G[u][v] = t;
G[v][u] = t;
}
dijsktra(1, n);
int ans = d[n];
p[1] = -1;
for (int u = n; u != 1; u = p[u]) {
G[p[u]][u] = INF;
G[u][p[u]] *= -1;
}
dijsktra(1, n);
ans += d[n];
if (ans >= INF)
puts("Back to jail");
else
printf("%d\n", ans);
}
}
/*
2
1
1 2 999
3
3
1 3 10
2 1 20
3 2 50
9
12
1 2 10
1 3 10
1 4 10
2 5 10
3 5 10
4 5 10
5 7 10
6 7 10
7 8 10
6 9 10
7 9 10
8 9 10
0

*/