解題區/解題區 - UVa

UVa 1048 - Low Cost Air Travel

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
3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
1 
2 1 3 
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
0

Sample Output

1
2
3
4
5
6
Case 1, Trip 1: Cost = 225
  Tickets used: 1
Case 2, Trip 1: Cost = 100
  Tickets used: 2
Case 2, Trip 2: Cost = 300
  Tickets used: 3 1

Solution

建圖方面相當麻煩，特別小心，有可能會在行程外的地點換組合票使用。

每個點的狀態為 (i, j)，表示完成行程中第 i 個目的地，當前位置在地圖編號 j。因此針對每一個組合票，嘗試建造從行程中的第 i 個目的地，到下一個目的地。

隨後求最短路徑。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <map>
using namespace std;
const int MAXNT = 32767;
vector<int> route[MAXNT];
int NTc[MAXNT], NT;
struct Edge {
    int to, w, label;
    Edge(int a = 0, int b = 0, int c = 0):
        to(a), w(b), label(c) {}
};
vector<Edge> g[MAXNT];
map< pair<int, int>, int> Rid;
int getId(pair<int, int> x) {
    if (Rid.count(x))
        return Rid[x];
    int &r = Rid[x];
    return r = Rid.size();
}
pair<int, int> dist[MAXNT];
int pre[MAXNT][2], inq[MAXNT];
void spfa(int st) {
    memset(dist, 63, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    memset(inq, 0, sizeof(inq));
    
    int u, v;
    queue<int> Q;
    
    Q.push(st), dist[st] = pair<int, int>(0, 0);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to;
            if (dist[v] > pair<int, int>(dist[u].first + g[u][i].w, dist[u].second+1)) {
                dist[v] = pair<int, int>(dist[u].first + g[u][i].w, dist[u].second+1);
                pre[v][0] = u, pre[v][1] = g[u][i].label;
                if (!inq[v]) {
                    inq[v] = 1, Q.push(v);
                }
            }
        }
    }
}
void solve(int N, int A[]) {
    for (int i = 0; i < MAXNT; i++) 
        g[i].clear();
    Rid.clear();
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < NT; j++) {
            int st = i, ed = i;
            for (int k = 0; k < route[j].size(); k++) {
                if (ed+1 < N && route[j][k] == A[ed+1])
                    ed++;
                int u = getId(pair<int, int>(st, route[j][0]));
                int v = getId(pair<int, int>(ed, route[j][k]));
                g[u].push_back(Edge(v, NTc[j], j));
//				printf("[%d] %d -> %d\n", j, u, v);
                if (ed == N)
                    break;
            }
        }
    }
    
    int st = getId(pair<int, int>(0, A[0]));
    int ed = getId(pair<int, int>(N-1, A[N-1]));
    spfa(st);
    
    vector<int> buy;
    for (int i = ed; i >= 0; i = pre[i][0])
        buy.push_back(pre[i][1]);
    printf("Cost = %d\n", dist[ed].first);
    printf("  Tickets used:");
    for (int i = (int) buy.size() - 2; i >= 0; i--)
        printf(" %d", buy[i]+1);
    puts("");
}
int main() {
    int N, Q, cases = 0;
    int A[MAXNT];
    while (scanf("%d", &NT) == 1 && NT) {
        for (int i = 0; i < NT; i++) {
            int m, x;
            scanf("%d %d", &NTc[i], &m);
            route[i].clear();
            for (int j = 0; j < m; j++) {
                scanf("%d", &x);
                route[i].push_back(x);
            }
        }
        
        scanf("%d", &Q), ++cases;
        for (int i = 0; i < Q; i++) {
            scanf("%d", &N);
            for (int j = 0; j < N; j++)
                scanf("%d", &A[j]);
            printf("Case %d, Trip %d: ", cases, i+1);
            solve(N, A);
        }
    }
    return 0;
} 
/*
3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
3
2 1 3 
1 1
0
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
0
*/