Submission #02224

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long int64;
typedef pair< int64, int64 > Pi;
struct edge {
int to, cost;
};
const int64 INF = 1LL << 58;
int64 N, M, K, S, P, Q, Zonbi[1000000];
vector< edge > graph[1000000];
int A[1000000], B[1000000];
int Denger[1000000];
vector< int > normal[100000];
void BFS()
{
queue< int > Que;
vector< int64 > min_cost(N, INF);
for(int i = 0; i < N; i++) {
if(Zonbi[i]) {
Que.push(i);
min_cost[i] = 0;
}
}
while(!Que.empty()) {
int p = Que.front(); Que.pop();
for(int i = 0; i < normal[p].size(); i++) {
int v = normal[p][i];
if(min_cost[v] != INF) continue;
min_cost[v] = min_cost[p] + 1;
Que.push(v);
}
}
for(int i = 1; i < N - 1; i++) {
if(min_cost[i] <= S) {
Denger[i] = true;
}
}
}
int Dijkstra()
{
vector< int > min_cost(100000, INF);
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
que.push(Pi(0, 0));
min_cost[0] = 0;
while(!que.empty()) {
int now = que.top().second;
int cost = que.top().first;
que.pop();
if(now == N - 1) return(cost);
if(cost > min_cost[now]) continue;
for(int i = 0; i < graph[now].size(); i++) {
edge e = graph[now][i];
if(Zonbi[e.to]) continue;
if(cost + e.cost < min_cost[e.to]) {
min_cost[e.to] = cost + e.cost;
que.push(Pi(min_cost[e.to], e.to));
}
}
}
return(-1);
}
signed main()
{
cin >> N >> M >> K >> S;
cin >> P >> Q;
for(int i = 0; i < K; i++) {
int C;
cin >> C;
--C;
Zonbi[C] = true;
}
for(int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
--A[i], --B[i];
normal[A[i]].push_back(B[i]);
normal[B[i]].push_back(A[i]);
}
BFS();
for(int i = 0; i < M; i++) {
int cost = P;
if(Denger[B[i]]) cost = Q;
if(B[i] == 0 || B[i] == N - 1) cost = 0;
graph[A[i]].push_back((edge){B[i], cost});
cost = P;
if(Denger[A[i]]) cost = Q;
if(A[i] == 0 || A[i] == N - 1) cost = 0;
graph[B[i]].push_back((edge){A[i], cost});
}
cout << Dijkstra() << endl;
}

ステータス

項目 データ
問題 0261 - ゾンビ島 (Zombie Island)
ユーザー名 ei1333
投稿日時 2015-12-13 23:45:15
言語 C++11
状態 Accepted
得点 5
ソースコード長 2223 Byte
最大実行時間 200 ms
最大メモリ使用量 57344 KB

セット

セット 得点 Cases
1 INPUT1 1 / 1 *in1.txt
2 INPUT2 1 / 1 *in2.txt
3 INPUT3 1 / 1 *in3.txt
4 INPUT4 1 / 1 *in4.txt
5 INPUT5 1 / 1 *in5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2016-yo-t5-in1.txt AC 20 ms 36060 KB
1
2016-yo-t5-in2.txt AC 85 ms 48676 KB
2
2016-yo-t5-in3.txt AC 21 ms 36552 KB
3
2016-yo-t5-in4.txt AC 200 ms 57344 KB
4
2016-yo-t5-in5.txt AC 148 ms 53072 KB
5
2016-yo-t5-in_s1.txt AC 27 ms 36036 KB
2016-yo-t5-in_s2.txt AC 26 ms 35996 KB