Submission #39305

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define INF 1000000000000000000LL
typedef pair<long long,int>P;
int n,m,k,s,p,q;
vector<int>node[100009];
int f[100009];
long long min_cnt[100009];
long long min_cost[100009];
int main(){
scanf("%d %d %d %d",&n,&m,&k,&s);
scanf("%d %d",&p,&q);
for(int i=0;i<=n;i++){
min_cost[i]=INF;
min_cnt[i]=INF;
}
for(int i=0;i<k;i++){
int c;
scanf("%d",&c);
f[c]=1;
node[0].push_back(c);
}
for(int i=0;i<m;i++){
int a,b;
scanf("%d %d",&a,&b);
node[a].push_back(b);
node[b].push_back(a);
}
queue<P>que;
que.push(P(0,-1));
while(!que.empty()){
P now=que.front();que.pop();
int pos=now.fi;
int cnt=now.se;
if(f[pos]==0||f[pos]==2){
if(min_cnt[pos]>cnt){
f[pos]=2;
min_cnt[pos]=cnt;
}
else continue;
}
if(cnt==s)continue;
for(int i=0;i<node[pos].size();i++){
int next=node[pos][i];
que.push(P(next,cnt+1));
}
}
priority_queue<P,vector<P>,greater<P> >pq;
pq.push(P(0,1));
min_cost[1]=0;
while(!pq.empty()){
P now=pq.top();pq.pop();
long long cost=now.fi;
int pos=now.se;
for(int i=0;i<node[pos].size();i++){
int next=node[pos][i];
long long ncost=(f[next]?q:p);
if(f[next]==1)continue;
if(next==n)ncost=0;
if(min_cost[next]>cost+ncost){
min_cost[next]=cost+ncost;
pq.push(P(cost+ncost,next));
}
}
}
printf("%lld\n",min_cost[n]);
return(0);
}

ステータス

項目 データ
問題 0261 - ゾンビ島 (Zombie Island)
ユーザー名 r1705
投稿日時 2018-07-23 09:22:06
言語 C++11
状態 Accepted
得点 5
ソースコード長 1584 Byte
最大実行時間 88 ms
最大メモリ使用量 15004 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 44 ms 2912 KB
1
2016-yo-t5-in2.txt AC 53 ms 8972 KB
2
2016-yo-t5-in3.txt AC 27 ms 4320 KB
3
2016-yo-t5-in4.txt AC 77 ms 13756 KB
4
2016-yo-t5-in5.txt AC 88 ms 15004 KB
5
2016-yo-t5-in_s1.txt AC 31 ms 9236 KB
2016-yo-t5-in_s2.txt AC 25 ms 9284 KB