Contents
Problem
司機要從起點到目的地，開車時間不得連續超過 10 小時，中途可以在有旅館的城市休息一晚。
請計算出花費最少天的走法(只需輸出天數)。
Solution
由於不能超過 600 分鐘的規定，原先可以到的城市路徑，不一定能達成。
所以先以 各旅館所在的城市、起點、終點，作為起始，找出它們到各個城市的最短路。
(可用 Dijkstra 或 SPFA)
接著我們就只需要關注以上三者，因為如果能不住旅館就到達，那起點和終點之間的路就小於 601。
以此類推，建一張新的圖，只要這三者之間的時間小於 601 ，就在新的圖建一條邊，權重設為 1 。
最後再利用 Floyd-Warshall 或 BFS 去找起點到終點所需的最少天數。
Code
SPFA1
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
using namespace std;
struct node
{
int v, w;
node(int a, int b) : v(a), w(b) {}
};
vector<node> adj_list[N]; //[i]: i -> v, time: w
int n; //number of cities
int n_to_hotel[N]; //map, index to city id which has hotel. (1: 1, 2: n)
int hotel[105][105] = {}; //the new adj_matrix of hotels(include 1 and n)
int d[N]; //time from source to each city
bool inQ[N];
//int parent[N]; 不處理反而比較快
void SPFA(int source)
{
//init
memset(inQ, false, sizeof inQ);
fill(d, d + n + 1, 1e9);
queue<node> Q;
Q.emplace(source, 0);
d[source] = 0;
while (!Q.empty())
{
int now = Q.front().v;
Q.pop();
inQ[now] = false;
for (node next : adj_list[now])
{
int tmp = d[now] + next.w;
if (tmp < d[next.v])
{
d[next.v] = tmp;
if (!inQ[next.v])
{
Q.emplace(next.v, tmp);
inQ[next.v] = true;
}
}
}
}
}
inline int input()
{
int n = 0;
char c;
while ((c = getchar()) != '\n' && c != ' ')
n = n * 10 + c - '0';
return n;
}
int main()
{
//freopen("test.out", "w", stdout);
int h, m;
while (scanf("%d", &n) && n)
{
scanf("%d ", &h);
int tmp, idx = 2;
//take 1 and n as a hotel for the convenience of the new adjacency matrix
n_to_hotel[1] = 1;
n_to_hotel[2] = n;
for (int i = 0; i < h; ++i)
{
//scanf("%d", &tmp);
tmp = input();
n_to_hotel[++idx] = tmp;
}
scanf("%d ", &m);
int u, v, w;
for (int i = 0; i < m; ++i)
{
//scanf("%d%d%d", &u, &v, &w);
u = input();
v = input();
w = input();
adj_list[u].emplace_back(v, w);
adj_list[v].emplace_back(u, w);
}
//build the new adj_matrix of hotels(include 1 and n)
for (int i = 1; i <= idx; ++i)
for (int j = 1; j <= idx; ++j)
hotel[i][j] = 1e9;
for (int i = 1; i <= idx; ++i)
{
hotel[i][i] = 0;
SPFA(n_to_hotel[i]);
for (int j = 1; j <= idx; ++j)
if (i != j && d[n_to_hotel[j]] <= E)
hotel[i][j] = 1;
}
//Floyd-Warshall
for (int k = 1; k <= idx; ++k)
for (int i = 1; i <= idx; ++i)
for (int j = 1; j <= idx; ++j)
if (hotel[i][k] + hotel[k][j] < hotel[i][j])
hotel[i][j] = hotel[i][k] + hotel[k][j];
//Minus one, since he does not need to spend the night in the destination (n).
printf("%d\n", hotel[1][2] != 1e9 ? (hotel[1][2] - 1) : -1);
//init
memset(hotel, 0, sizeof hotel);
for (int i = 1; i <= n; ++i)
adj_list[i].clear();
}
return 0;
}
Dijkstra1
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
using namespace std;
struct node
{
int v, w;
node(int a, int b) : v(a), w(b) {}
bool operator<(const node &a) const
{
return w > a.w;
}
};
vector<node> adj_list[N]; //[i]: i -> v, time: w
int n; //number of cities
int n_to_hotel[N]; //map, index to city id which has hotel. (1: 1, 2: n)
int hotel[105][105] = {}; //the new adj_matrix of hotels(include 1 and n)
bool visited[N]; //for dijkstra
int d[N]; //time from source to each city
void dijkstra(int source)
{
//init
memset(visited, 0, sizeof visited);
fill(d, d + n + 1, 1e9);
priority_queue<node> PQ;
PQ.emplace(source, 0);
d[source] = 0;
for (int i = 0; i < n - 1; ++i)
{
while (!PQ.empty() && visited[PQ.top().v])
PQ.pop();
if (PQ.empty())
break;
int now = PQ.top().v;
PQ.pop();
visited[now] = true;
for (node next : adj_list[now])
{
if (!visited[next.v]) //不檢查反而比較快...
{
int tmp = d[now] + next.w;
if (tmp < d[next.v])
{
d[next.v] = tmp;
PQ.emplace(next.v, tmp);
}
}
}
}
}
inline int input()
{
int n = 0;
char c;
while ((c = getchar()) != '\n' && c != ' ')
n = n * 10 + c - '0';
return n;
}
int main()
{
//freopen("test.out", "w", stdout);
int h, m;
while (scanf("%d", &n) && n)
{
scanf("%d ", &h);
int tmp, idx = 2;
//take 1 and n as a hotel for the convenience of the new adjacency matrix
n_to_hotel[1] = 1;
n_to_hotel[2] = n;
for (int i = 0; i < h; ++i)
{
//scanf("%d", &tmp);
tmp = input();
n_to_hotel[++idx] = tmp;
}
scanf("%d ", &m);
int u, v, w;
for (int i = 0; i < m; ++i)
{
//scanf("%d%d%d", &u, &v, &w);
u = input();
v = input();
w = input();
adj_list[u].emplace_back(v, w);
adj_list[v].emplace_back(u, w);
}
//build the new adj_matrix of hotels(include 1 and n)
for (int i = 1; i <= idx; ++i)
for (int j = 1; j <= idx; ++j)
hotel[i][j] = 1e9;
for (int i = 1; i <= idx; ++i)
{
hotel[i][i] = 0;
dijkstra(n_to_hotel[i]);
for (int j = 1; j <= idx; ++j)
if (i != j && d[n_to_hotel[j]] <= E)
hotel[i][j] = 1;
}
//Floyd-Warshall
for (int k = 1; k <= idx; ++k)
for (int i = 1; i <= idx; ++i)
for (int j = 1; j <= idx; ++j)
if (hotel[i][k] + hotel[k][j] < hotel[i][j])
hotel[i][j] = hotel[i][k] + hotel[k][j];
//Minus one, since he does not need to spend the night in the destination (n).
printf("%d\n", hotel[1][2] != 1e9 ? (hotel[1][2] - 1) : -1);
//BFS
/*queue<int> Q;
int day[105] = {};
bool visited[105] = {true, true}, flag = true;
fill(day, day + idx + 1, 1e9);
day[1] = 0;
Q.push(1);
while (!Q.empty() && flag)
{
int now = Q.front();
Q.pop();
for (int i = 1; i <= idx; ++i)
if (!visited[i] && hotel[now][i] == 1)
{
if (i == 2)
{
day[2] = day[now];
flag = false;
break;
}
day[i] = day[now] + 1;
visited[i] = true;
Q.push(i);
}
}
printf("%d\n", day[2] != 1e9 ? day[2] : -1);
*/
//init
memset(hotel, 0, sizeof hotel);
for (int i = 1; i <= n; ++i)
adj_list[i].clear();
}
return 0;
}