Submission #17593

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
struct Node {
int idx, val, ticket;
bool operator<(const Node &r) const {
if(val == r.val) {
return ticket < r.ticket;
} else {
return val > r.val;
}
}
};
struct Edge {
int to, cost;
};
int main() {
int c, n, m, s, d;
Node node[101][11];
vector<Edge> edge[101];
cin >> c >> n >> m >> s >> d;
for(int i = 0; i < m; ++i) {
int a, b, f;
cin >> a >> b >> f;
edge[a].push_back((Edge){ b, f });
edge[b].push_back((Edge){ a, f });
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= c; ++j) {
node[i][j] = (Node){ i, INF, j };
}
}
priority_queue<Node> q;
node[s][c].val = 0;
q.push(node[s][c]);
while(!q.empty()) {
Node now = q.top(); q.pop();
for(int i = 0; i < edge[now.idx].size(); ++i) {
Edge &e = edge[now.idx][i];
Node &next0 = node[e.to][now.ticket];
int ncost;
ncost = now.val + e.cost;
if(ncost < next0.val) {
next0.val = ncost;
q.push((Node){ e.to, ncost, now.ticket });
}
if(now.ticket) {
Node &next1 = node[e.to][now.ticket - 1];
ncost = now.val + e.cost / 2;
if(ncost < next1.val) {
next1.val = ncost;
q.push((Node){ e.to, ncost, now.ticket - 1 });
}
}
}
}
int ans = INF;
for(int i = 0; i <= c; ++i) {
ans = min(ans, node[d][i].val);
}
cout << ans << endl;
/*
for(int i = 0 ; i <= c; ++i) {
cout << node[2][i].val << endl;
}
*/
}

ステータス

項目 データ
問題 0717 - 高速バス
ユーザー名 ei1503
投稿日時 2017-05-15 17:58:29
言語 C++11
状態 Accepted
得点 5
ソースコード長 1372 Byte
最大実行時間 16 ms
最大メモリ使用量 620 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01.txt AC 12 ms 480 KB
1
input02.txt AC 11 ms 420 KB
1
input03.txt AC 12 ms 496 KB
1
input04.txt AC 12 ms 568 KB
1
input05.txt AC 13 ms 620 KB
1
input06.txt AC 11 ms 548 KB
1
input07.txt AC 16 ms 476 KB
1
input08.txt AC 11 ms 528 KB
1
input09.txt AC 10 ms 568 KB
1
input10.txt AC 10 ms 500 KB
1