Submission #00005

ソースコード

?
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
#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;
map<int,bool> used;
vector<P> to[100001];
long long tree[100001]={0};
main(){
cin>>n>>m>>x;
for(int i=1;i<=n;i++){
cin>>tree[i];
}
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();
used[nowtree]=true;
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(!used[nexttree]){
que.push(lP(nowcost+cost,P(nexttree,nowtail-cost)));
}
}
}
else if(nowtail-cost>tree[nexttree]){
if(!used[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(!used[nexttree]){
que.push(lP(nowcost+(cost-nowtail)+cost,P(nexttree,0)));
}
}
}
}
}
}
cout<<-1<<endl;
}

ステータス

項目 データ
問題 0001 - フクロモモンガ (Sugar Glider)
ユーザー名 ei1417
投稿日時 2016-01-20 17:24:49
言語 C++11
状態 Time Limit Exceeded
得点 25
ソースコード長 1687 Byte
最大実行時間 2000 ms
最大メモリ使用量 262144 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt AC 16 ms 2908 KB
1
3
01-02.txt AC 14 ms 3036 KB
1
3
01-03.txt AC 17 ms 2988 KB
1
3
01-04.txt AC 14 ms 2952 KB
1
3
01-05.txt AC 14 ms 3048 KB
1
3
01-06.txt AC 12 ms 2972 KB
1
3
01-07.txt AC 16 ms 3028 KB
1
3
01-08.txt AC 14 ms 3040 KB
1
3
01-09.txt AC 14 ms 3004 KB
1
3
01-10.txt AC 16 ms 3076 KB
1
3
01-11.txt AC 15 ms 2888 KB
1
3
01-12.txt AC 14 ms 3200 KB
1
3
01-13.txt AC 22 ms 3168 KB
1
3
01-14.txt AC 14 ms 2888 KB
1
3
01-15.txt AC 16 ms 3252 KB
1
3
01-16.txt AC 14 ms 3016 KB
1
3
01-17.txt AC 14 ms 3140 KB
1
3
01-18.txt AC 14 ms 3032 KB
1
3
01-19.txt AC 13 ms 3016 KB
1
3
01-20.txt AC 15 ms 2900 KB
1
3
02-01.txt AC 307 ms 19100 KB
2
3
02-02.txt TLE 2000 ms 32916 KB
2
3
02-03.txt AC 254 ms 14424 KB
2
3
02-04.txt AC 1427 ms 32220 KB
2
3
02-05.txt TLE 2000 ms 31704 KB
2
3
02-06.txt AC 23 ms 3688 KB
2
3
02-07.txt AC 282 ms 19168 KB
2
3
02-08.txt AC 552 ms 26736 KB
2
3
02-09.txt AC 269 ms 18728 KB
2
3
02-10.txt AC 187 ms 14432 KB
2
3
02-11.txt AC 42 ms 5264 KB
2
3
02-12.txt AC 292 ms 19516 KB
2
3
02-13.txt TLE 2000 ms 24612 KB
2
3
02-14.txt AC 274 ms 19140 KB
2
3
02-15.txt AC 19 ms 3532 KB
2
3
02-16.txt TLE 2000 ms 33548 KB
2
3
02-17.txt AC 43 ms 5148 KB
2
3
02-18.txt AC 45 ms 4692 KB
2
3
02-19.txt AC 116 ms 9452 KB
2
3
02-20.txt AC 51 ms 6120 KB
2
3
03-01.txt AC 251 ms 18032 KB
3
03-02.txt AC 54 ms 5300 KB
3
03-03.txt AC 217 ms 16848 KB
3
03-04.txt AC 247 ms 13428 KB
3
03-05.txt MLE 2000 ms 262144 KB
3
03-06.txt AC 35 ms 3944 KB
3
03-07.txt AC 357 ms 24456 KB
3
03-08.txt AC 753 ms 28952 KB
3
03-09.txt AC 461 ms 21660 KB
3
03-10.txt AC 318 ms 32924 KB
3
03-11.txt AC 62 ms 6700 KB
3
03-12.txt AC 465 ms 25484 KB
3
03-13.txt AC 289 ms 19420 KB
3
03-14.txt AC 305 ms 19964 KB
3
03-15.txt AC 256 ms 19352 KB
3
03-16.txt AC 615 ms 30232 KB
3
03-17.txt AC 96 ms 8604 KB
3
03-18.txt AC 21 ms 3768 KB
3
03-19.txt AC 277 ms 19364 KB
3
03-20.txt AC 71 ms 6204 KB
3
sample-01.txt AC 15 ms 3312 KB
sample-02.txt AC 12 ms 3244 KB
sample-03.txt AC 13 ms 3052 KB