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