Submission #10941

ソースコード

?
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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, m, x;
int t[11111];
struct edge {
int t, c;
edge() {}
edge(int t, int c) :
t(t), c(c) {}
};
typedef long long ll;
struct state {
int n, s, t;
ll c;
state() {}
state(int n, int s, int t, ll c) :
n(n), s(s), t(t), c(c) {}
bool operator>(const state& e) const {
return c > e.c;
}
};
vector<edge> es[11111];
ll co[11111][2][222];
int main(void) {
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i++) {
scanf("%d", t+i);
if (t[i] == 2) t[i] = 1;
else if (t[i] == 1) t[i] = 2;
}
for (int i = 0; i < m; i++) {
int a, b, d; scanf("%d%d%d", &a, &b, &d); --a; --b;
es[a].emplace_back(b, d);
es[b].emplace_back(a, d);
}
priority_queue<state, vector<state>, greater<state>> q;
q.emplace(0, t[0], x, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k <= x; k++) co[i][j][k] = 1ll<<45;
}
}
co[0][t[0]][x] = 0;
while (!q.empty()) {
state p = q.top(); q.pop();
// printf("%d %d %d %lld\n", p.n, p.s, p.t, p.c);
if (p.n == n-1) {
printf("%lld\n", p.c);
return 0;
}
if (co[p.n][p.s][p.t] < p.c) continue;
for (auto&& e : es[p.n]) {
int ns, nt;
if (t[e.t] < 2) {
if (p.t-e.c > 0 && p.s != t[e.t]) continue;
ns = t[e.t];
nt = x;
} else {
ns = p.s;
nt = max(0, p.t-e.c);
}
if (co[e.t][ns][nt] > p.c+e.c) {
co[e.t][ns][nt] = p.c+e.c;
q.emplace(e.t, ns, nt, p.c+e.c);
}
}
}
return 0;
}

ステータス

項目 データ
問題 0597 - ヘビの JOI 君 (Snake JOI)
ユーザー名 💩
投稿日時 2016-12-11 16:43:28
言語 C++11
状態 Accepted
得点 1
ソースコード長 1694 Byte
最大実行時間 37 ms
最大メモリ使用量 36312 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 33 ms 30048 KB
1
2017-yo-t6-in2.txt AC 26 ms 34288 KB
2
2017-yo-t6-in3.txt AC 31 ms 36284 KB
3
2017-yo-t6-in4.txt AC 31 ms 36296 KB
4
2017-yo-t6-in5.txt AC 37 ms 36312 KB
5