解題區/解題區 - 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
*/