Submission #00022

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define INF 1000000000
typedef pair<int,int>P;
vector<P>node[100009];
int min_cost[100009],ans[100009];
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<=n;i++){
min_cost[i]=INF;
ans[i]=INF;
}
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
node[b].push_back(P(a,c));
}
for(int i=0;i<k;i++){
int t;
cin>>t;
node[0].push_back(P(t,0));
ans[t]=t;
}
priority_queue<P,vector<P>,greater<P> >pq;
pq.push(P(0,0));
min_cost[0]=0;
while(!pq.empty()){
P now=pq.top();pq.pop();
int cost=now.fi;
int pos=now.se;
for(int i=0;i<node[pos].size();i++){
int next=node[pos][i].fi;
int ncost=node[pos][i].se;
if(cost+ncost<min_cost[next]){
min_cost[next]=cost+ncost;
if(pos!=0)ans[next]=ans[pos];
pq.push(P(cost+ncost,next));
}
else if(cost+ncost==min_cost[next]){
if(pos!=0&&ans[pos]<ans[next]){
ans[next]=ans[pos];
}
}
}
}
for(int i=1;i<=n;i++){
if(ans[i]==INF){
cout<<-1<<endl;
}
else{
cout<<ans[i]<<endl;
}
}
return(0);
}

ステータス

項目 データ
問題 0003 - 避難 (Evacuation)
ユーザー名 r1705
投稿日時 2019-02-28 15:02:41
言語 C++11
状態 Accepted
得点 6
ソースコード長 1213 Byte
最大実行時間 420 ms
最大メモリ使用量 12748 KB

セット

セット 得点 Cases
1 SubTask-A 1.2 / 1.2 input-A*
2 SubTask-B 4.8 / 4.8 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-A01 AC 30 ms 2908 KB
1
2
input-A02 AC 23 ms 2676 KB
1
2
input-A03 AC 20 ms 2700 KB
1
2
input-A04 AC 26 ms 2868 KB
1
2
input-A05 AC 26 ms 2784 KB
1
2
input-A06 AC 29 ms 2824 KB
1
2
input-A07 AC 20 ms 2820 KB
1
2
input-A08 AC 32 ms 2976 KB
1
2
input-A09 AC 26 ms 2924 KB
1
2
input-A10 AC 22 ms 3028 KB
1
2
input-A11 AC 96 ms 2952 KB
1
2
input-A12 AC 18 ms 2884 KB
1
2
input-A13 AC 31 ms 2808 KB
1
2
input-B01 AC 21 ms 2852 KB
2
input-B02 AC 24 ms 2872 KB
2
input-B03 AC 47 ms 3276 KB
2
input-B04 AC 33 ms 3264 KB
2
input-B05 AC 62 ms 4404 KB
2
input-B06 AC 68 ms 4472 KB
2
input-B07 AC 147 ms 5168 KB
2
input-B08 AC 159 ms 5588 KB
2
input-B09 AC 153 ms 5848 KB
2
input-B10 AC 155 ms 6100 KB
2
input-B11 AC 263 ms 9040 KB
2
input-B12 AC 274 ms 9240 KB
2
input-B13 AC 227 ms 7244 KB
2
input-B14 AC 420 ms 12748 KB
2
input-B15 AC 392 ms 12320 KB
2
input-B16 AC 409 ms 12568 KB
2
input-B17 AC 255 ms 10928 KB
2
input-B18 AC 28 ms 6948 KB
2
input-sample01 AC 22 ms 6936 KB
2
input-sample02 AC 24 ms 6984 KB
2
input-sample03 AC 20 ms 7036 KB
2