Submission #34605

ソースコード

?
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 <bits/stdc++.h>
#define debug(); printf("Check\n");
#define INF (1 << 30)
using namespace std;
typedef pair<int, int>P;
typedef pair<P, int>PP;
vector<P>graph[101];
priority_queue<PP, vector<PP>, greater<PP>>p_que;
int min_cost[11][100];
int c, n, m, s, d;
int a, b, f; // 何でもかんでも大域変数、気持ちいいです
int main()
{
for ( int i = 0; i < 11; i++) {
for ( int j = 0; j < 100; j++) {
min_cost[i][j] = INF;
}
}
scanf("%d %d %d %d %d", &c, &n, &m, &s, &d); s--; d--;
for ( int i = 0; i < m; i++) {
scanf("%d %d %d", &a, &b, &f); a--; b--;
graph[a].push_back(P(f, b));
graph[b].push_back(P(f, a));
}
for ( int i = 0; i <= 10; i++) {
min_cost[i][s] = 0;
}
p_que.push(PP(P(0, c), s));
while( !p_que.empty() ) {
PP now = p_que.top(); p_que.pop();
int ticket = now.first.second;
int cost = now.first.first;
int pos = now.second;
for ( int i = 0; i < graph[pos].size(); i++) {
int ncos = cost + graph[pos][i].first;
int npos = graph[pos][i].second;
if ( ncos < min_cost[ticket][npos] ) {
min_cost[ticket][npos] = ncos;
p_que.push(PP(P(ncos, ticket), npos));
}
if ( ticket > 0 ) {
ncos = cost + (graph[pos][i].first / 2);
if ( ncos < min_cost[ticket - 1][npos]) {
min_cost[ticket - 1][npos] = ncos;
p_que.push(PP(P(ncos, ticket - 1), npos));
}
}
}
}
int ans = INF;
for ( int i = 0; i <= 10; i++ ) {
if ( ans > min_cost[i][d] ) {
ans = min_cost[i][d];
}
}
printf("%d\n", ans);
return 0;
}

ステータス

項目 データ
問題 0717 - 高速バス
ユーザー名 ei1710
投稿日時 2018-05-03 12:56:33
言語 C++11
状態 Accepted
得点 5
ソースコード長 1924 Byte
最大実行時間 31 ms
最大メモリ使用量 604 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01.txt AC 21 ms 480 KB
1
input02.txt AC 28 ms 436 KB
1
input03.txt AC 29 ms 528 KB
1
input04.txt AC 18 ms 604 KB
1
input05.txt AC 27 ms 540 KB
1
input06.txt AC 29 ms 480 KB
1
input07.txt AC 28 ms 552 KB
1
input08.txt AC 21 ms 484 KB
1
input09.txt AC 20 ms 520 KB
1
input10.txt AC 31 ms 472 KB
1