Submission #00006

ソースコード

?
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
#include<bits/stdc++.h>
#define F first
#define S second
#define LLINF (1LL<<60)
using namespace std;
typedef pair<int,long long> P;
typedef pair<long long,P> lP;
long long n,m,x;
vector<P> to[100001];
long long tree[100001]={0};
long long mins[100001];
main(){
cin>>n>>m>>x;
for(int i=1;i<=n;i++){
cin>>tree[i];
mins[i]=LLINF;
}
for(int i=0;i<m;i++){
long long a,b,c;
cin>>a>>b>>c;
to[a].push_back(P(b,c));
to[b].push_back(P(a,c));
}
priority_queue<lP,vector<lP>,greater<lP> > que;
que.push(lP(0,P(1,x)));
while(!que.empty()){
long long nowcost=que.top().F,nowtree=que.top().S.F,nowtail=que.top().S.S;
que.pop();
if(nowtree==n){
cout<<nowcost<<endl;
return 0;
}
for(int i=0;i<to[nowtree].size();i++){
long long nexttree=to[nowtree][i].F;
long long cost=to[nowtree][i].S;
if(tree[nowtree]>=cost){
if(nowtail-cost>=0&&nowtail-cost<=tree[nexttree]){
if(nexttree==n){
que.push(lP(nowcost+cost+(tree[nexttree]-(nowtail-cost)),P(nexttree,tree[nexttree])));
}
else{
if(mins[nexttree]>nowcost+cost){
mins[nexttree]=nowcost+cost;
que.push(lP(nowcost+cost,P(nexttree,nowtail-cost)));
}
}
}
else if(nowtail-cost>tree[nexttree]){
if(mins[nexttree]>nowcost+cost+(nowtail-cost-tree[nexttree])){
mins[nexttree]=nowcost+cost+(nowtail-cost-tree[nexttree]);
que.push(lP(nowcost+cost+(nowtail-cost-tree[nexttree]),P(nexttree,tree[nexttree])));
}
}
else if(nowtail-cost<0){
if(nexttree==n){
que.push(lP(nowcost+(cost-nowtail)+cost+tree[nexttree],P(nexttree,tree[nexttree])));
}
else{
if(mins[nexttree]>nowcost+(cost-nowtail)+cost){
mins[nexttree]=nowcost+(cost-nowtail)+cost;
que.push(lP(nowcost+(cost-nowtail)+cost,P(nexttree,0)));
}
}
}
}
}
}
cout<<-1<<endl;
}

ステータス

項目 データ
問題 0001 - フクロモモンガ (Sugar Glider)
ユーザー名 ei1417
投稿日時 2016-01-20 17:28:36
言語 C++11
状態 Accepted
得点 100
ソースコード長 1921 Byte
最大実行時間 310 ms
最大メモリ使用量 22464 KB

セット

セット 得点 Cases
1 Subtask1 25 / 25 01-*
2 Subtask2 25 / 25 02-*
3 Subtask3 50 / 50 01-*, 02-*, 03-*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt AC 13 ms 2908 KB
1
3
01-02.txt AC 14 ms 3272 KB
1
3
01-03.txt AC 15 ms 3120 KB
1
3
01-04.txt AC 12 ms 2972 KB
1
3
01-05.txt AC 13 ms 2944 KB
1
3
01-06.txt AC 14 ms 2880 KB
1
3
01-07.txt AC 11 ms 2792 KB
1
3
01-08.txt AC 17 ms 3064 KB
1
3
01-09.txt AC 13 ms 2912 KB
1
3
01-10.txt AC 16 ms 3040 KB
1
3
01-11.txt AC 13 ms 2784 KB
1
3
01-12.txt AC 16 ms 3084 KB
1
3
01-13.txt AC 14 ms 3068 KB
1
3
01-14.txt AC 17 ms 2916 KB
1
3
01-15.txt AC 13 ms 3168 KB
1
3
01-16.txt AC 11 ms 2928 KB
1
3
01-17.txt AC 13 ms 2920 KB
1
3
01-18.txt AC 12 ms 2944 KB
1
3
01-19.txt AC 11 ms 2932 KB
1
3
01-20.txt AC 12 ms 2948 KB
1
3
02-01.txt AC 310 ms 20072 KB
2
3
02-02.txt AC 236 ms 20964 KB
2
3
02-03.txt AC 165 ms 11764 KB
2
3
02-04.txt AC 265 ms 22464 KB
2
3
02-05.txt AC 215 ms 20296 KB
2
3
02-06.txt AC 24 ms 3708 KB
2
3
02-07.txt AC 265 ms 19696 KB
2
3
02-08.txt AC 267 ms 18168 KB
2
3
02-09.txt AC 271 ms 19308 KB
2
3
02-10.txt AC 198 ms 15296 KB
2
3
02-11.txt AC 34 ms 4884 KB
2
3
02-12.txt AC 171 ms 14120 KB
2
3
02-13.txt AC 87 ms 11788 KB
2
3
02-14.txt AC 264 ms 19948 KB
2
3
02-15.txt AC 22 ms 3428 KB
2
3
02-16.txt AC 218 ms 20548 KB
2
3
02-17.txt AC 38 ms 4300 KB
2
3
02-18.txt AC 41 ms 4592 KB
2
3
02-19.txt AC 119 ms 9764 KB
2
3
02-20.txt AC 44 ms 5192 KB
2
3
03-01.txt AC 257 ms 18308 KB
3
03-02.txt AC 66 ms 5992 KB
3
03-03.txt AC 206 ms 17332 KB
3
03-04.txt AC 115 ms 9944 KB
3
03-05.txt AC 214 ms 19308 KB
3
03-06.txt AC 35 ms 4680 KB
3
03-07.txt AC 249 ms 17380 KB
3
03-08.txt AC 290 ms 21760 KB
3
03-09.txt AC 214 ms 17220 KB
3
03-10.txt AC 222 ms 20544 KB
3
03-11.txt AC 50 ms 5284 KB
3
03-12.txt AC 260 ms 20324 KB
3
03-13.txt AC 292 ms 19940 KB
3
03-14.txt AC 275 ms 19832 KB
3
03-15.txt AC 255 ms 20012 KB
3
03-16.txt AC 281 ms 21660 KB
3
03-17.txt AC 83 ms 7064 KB
3
03-18.txt AC 18 ms 3448 KB
3
03-19.txt AC 268 ms 19864 KB
3
03-20.txt AC 72 ms 6820 KB
3
sample-01.txt AC 11 ms 3092 KB
sample-02.txt AC 17 ms 3020 KB
sample-03.txt AC 11 ms 2948 KB