Submission #10946

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 INF = 1LL << 59;
struct edge
{
int to, cost;
};
struct node
{
int now, time, type;
};
int N, M, X, T[10000];
vector< edge > g[10000];
int64 min_cost[10000][202][3];
int bfs()
{
queue< node > qs[202];
fill_n(**min_cost, 10000 * 202 * 3, INF);
qs[0].emplace((node){0, 0, 1});
min_cost[0][0][1] = 0;
for(int t = 0; true; t++) {
auto& que = qs[t % 202];
while(!que.empty()) {
const node p = que.front();
que.pop();
if(t != min_cost[p.now][p.time][p.type]) continue;
if(p.now == N - 1) return(t);
for(auto e : g[p.now]) {
node q = (node){e.to, p.time, p.type};
if(q.type + T[e.to] == 3) {
if(q.time + e.cost < X) continue;
q.time = 0;
q.type = T[e.to];
} else if(q.type == T[e.to]) {
q.time = 0;
} else {
q.time = min(X, q.time + e.cost);
}
if(t + e.cost >= min_cost[q.now][q.time][q.type]) continue;
min_cost[q.now][q.time][q.type] = t + e.cost;
qs[(t + e.cost) % 202].push(q);
}
}
}
}
int main()
{
cin >> N >> M >> X;
for(int i = 0; i < N; i++) {
cin >> T[i];
if(T[i] == 0) T[i] = 1;
else if(T[i] == 1) T[i] = 0;
}
for(int i = 0; i < M; i++) {
int A, B, D;
cin >> A >> B >> D;
--A, --B;
g[A].emplace_back((edge){B, D});
g[B].emplace_back((edge){A, D});
}
cout << bfs() << endl;
}

ステータス

項目 データ
問題 0597 - ヘビの JOI 君 (Snake JOI)
ユーザー名 ei1333
投稿日時 2016-12-11 16:54:53
言語 C++11
状態 Accepted
得点 1
ソースコード長 1563 Byte
最大実行時間 42 ms
最大メモリ使用量 48948 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 42 ms 48736 KB
1
2017-yo-t6-in2.txt AC 40 ms 48808 KB
2
2017-yo-t6-in3.txt AC 41 ms 48948 KB
3
2017-yo-t6-in4.txt AC 40 ms 48920 KB
4
2017-yo-t6-in5.txt AC 38 ms 48884 KB
5