Submission #10953

ソースコード

?
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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,pair<ll,P> > PP;
ll n,m,x;
ll t[11111];
vector<P> e[11111];
ll d[11111][3][222];
int main(void){
scanf("%lld %lld %lld",&n,&m,&x);
for(int i = 0; i < n; i++){
scanf("%lld",t+i);
}
for(int j = 0; j < m; j++){
ll u,v,c;
scanf("%lld %lld %lld",&u,&v,&c);
u--;v--;
e[u].push_back(make_pair(v,c));
e[v].push_back(make_pair(u,c));
}
for(int i = 0; i < 11111; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 222; k++)
d[i][j][k] = 1LL<<60;
priority_queue<PP,vector<PP>, greater<PP> > que;
que.push(make_pair(0,make_pair(0,make_pair(0,x))));
d[0][0][x] = 0;
while(!que.empty()){
PP p = que.top();
ll c = p.F;
ll u = p.S.F;
ll f = p.S.S.F;
ll fx= p.S.S.S;
que.pop();
if(d[u][f][fx] < c) continue;
for(int i = 0; i < (int)e[u].size(); i++){
ll v = e[u][i].F;
ll cc= e[u][i].S;
if(t[v] != 1 && t[v] != f && fx > cc) continue;
if(t[v] == 1){
if(c+cc < d[v][f][max(0LL,fx-cc)]){
d[v][f][max(0LL,fx-cc)] = c+cc;
que.push(make_pair(c+cc,make_pair(v,make_pair(f,max(0LL,fx-cc)))));
}
}else{
if(c+cc < d[v][t[v]][x]){
d[v][t[v]][x] = c+cc;
que.push(make_pair(c+cc,make_pair(v,make_pair(t[v],x))));
}
}
}
}
ll best = 1LL<<60;
for(int i = 0; i < 222; i++){
best = min(best,d[n-1][0][i]);
best = min(best,d[n-1][1][i]);
best = min(best,d[n-1][2][i]);
}
printf("%lld\n",best);
}

ステータス

項目 データ
問題 0597 - ヘビの JOI 君 (Snake JOI)
ユーザー名 ei1133
投稿日時 2016-12-11 21:34:42
言語 C++11
状態 Accepted
得点 1
ソースコード長 1882 Byte
最大実行時間 60 ms
最大メモリ使用量 59864 KB

セット

セット 得点 Cases
1 set1 20 / 20 *t6*1.txt
2 set2 0 / 20 *t6*2.txt
3 set3 0 / 20 *t6*3.txt
4 set4 0 / 20 *t6*4.txt
5 set5 0 / 20 *t6*5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2017-yo-t6-in1.txt AC 60 ms 59612 KB
1
2017-yo-t6-in2.txt AC 42 ms 59672 KB
2
2017-yo-t6-in3.txt AC 46 ms 59656 KB
3
2017-yo-t6-in4.txt AC 59 ms 59764 KB
4
2017-yo-t6-in5.txt AC 47 ms 59864 KB
5