解題區►解題區 - UVa

UVa 12120 - Photographic Tour

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
3 2
0 1 1
0 2 2
3
1 1 2
3 2
0 1 1
0 2 2
1
1
0 0

Sample Output

1
2
Tour 1: 3
Tour 2: 0

Solution

紀錄兩個狀態，分別為起點到中繼點、中繼點到終點的結果。

起點到中繼點時，將記錄 dp1[i][j] 起點到中繼點 i，恰好使用第 j 張票。

終點到中繼點時，將記錄 dp2[i][j] 終點到中繼點 i，恰好使用第 n - j 張票。

隨後合併檢查是否中繼點可以構出一條路從起點到終點。

為了方便操作，將資料反轉丟入函數。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector< pair<int, int> > g[1024];
void bfs(int u, int A[], int An, int rg[][128]) {
	int t;
	queue<int> Q, T;
	Q.push(u), T.push(0);
	rg[u][0] = 1;
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		t = T.front(), T.pop();
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i].first;
			if (t < An && g[u][i].second == A[t]) {
				if (rg[v][t+1] == 0)  {
					rg[v][t+1] = 1;
					Q.push(v), T.push(t+1);
				}
			}
		}
	}
}
int main() {
	int n, m, t, cases = 0;
	int x, y, z, A[128]; 
	int g1[128][128], g2[128][128];
	while (scanf("%d %d", &n, &m) == 2 && n) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &z);
			g[x].push_back(make_pair(y, z));
			g[y].push_back(make_pair(x, z));
		}
		scanf("%d", &t);
		for (int i = 0; i < t; i++)
			scanf("%d", &A[i]);
		
		memset(g1, 0, sizeof(g1));
		memset(g2, 0, sizeof(g2));
		bfs(0, A, t, g1);
		reverse(A, A+t);
		bfs(n-1, A, t, g2);
		int ret = 0;
		for (int i = 0; i < n; i++) {
			int ok = 0;
			for (int j = 0; j <= t; j++)
				ok |= g1[i][j] && g2[i][t - j];
			ret += ok;
		}
		printf("Tour %d: %d\n", ++cases, ret);
	}
	return 0;
}
/*
3 2
0 1 1
0 2 2
3
1 1 2
3 2
0 1 1
0 2 2
1
1
0 0
*/