解題區►解題區 - UVa

UVa 12878 - Flowery Trails

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在國家公園的步行路道上要在兩側放置花卉，而主辦單位認為只要在其中兩個重要景點的最短路徑上的道路放置即可。通常大部分人只會走最短路徑。

請問總花費為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1

Sample Output

1
2
3860
18

Solution

最短路徑可能有數條，因此要窮舉每一條邊是否在最短路徑上，已知景點分別為 st 和 ed ，那麼找到 st -> u 和 ed -> v 的單源最短路徑，接下來窮舉 u -> v ，加上 st -> u 和 v -> ed ，得到 st -> u -> v -> ed 的最少花費，檢查是否等於最短路徑長即可。

這一題是雙向圖，如果是單向圖則要反轉邊，才能對 ed 進行單源最短路徑 (SSSP)。在這一題寫 SSSP 使用 SPFA 算法，也許 dijkstra 也是挺不錯的。

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
 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm> 
using namespace std;
#define MAXN 32767
vector< pair<int, int> > g[MAXN];
int dist1[MAXN], dist2[MAXN];
void spfa(int st, int ed, int dist[]) {
	static int inq[MAXN];
	queue<int> Q;
	int u, v, w;
	dist[st] = 0, Q.push(st);
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i].first, w = g[u][i].second;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				if (!inq[v])
					inq[v] = 1, Q.push(v);
			}
		}
	}
}
int main() {
	int n, m;
	int x, y, w;
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &w);
			g[x].push_back(make_pair(y, w));
			g[y].push_back(make_pair(x, w));
		}
		
		for (int i = 0; i < n; i++)
			dist1[i] = dist2[i] = 0x3f3f3f3f;
		spfa(0, n-1, dist1);
		spfa(n-1, 0, dist2);
	
		int sp = dist1[n - 1], ret = 0;
		for (int i = 0; i < n; i++) {
			x = i;
			for (int j = 0; j < g[i].size(); j++) {
				y = g[i][j].first, w = g[i][j].second;
				if (dist1[x] + w + dist2[y] == sp)
					ret += w;
			}
		}
		printf("%d\n", ret * 2);
	}
	return 0;
}
/*
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
*/