Submission #00026

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
typedef pair< int, int > Pi;
const int INF = 1 << 30;
struct edge {
int to, cost;
};
vector< edge > graph[3000];
int min_cost[3000];
int N, M, K;
void Dijkstra()
{
fill_n(min_cost, 3000, INF);
priority_queue< Pi, vector< Pi >, greater< Pi > > Que;
for(int i = 0; i < K; i++) {
int S;
cin >> S;
Que.push(Pi(0, --S));
min_cost[S] = 0;
}
while(!Que.empty()) {
Pi p = Que.top(); Que.pop();
if(min_cost[p.second] < p.first) continue;
for(auto e : graph[p.second]) {
int next = p.first + e.cost;
if(min_cost[e.to] > next) {
min_cost[e.to] = next;
Que.push(Pi(next, e.to));
}
}
}
}
int main()
{
cin >> N >> M >> K;
for(int i = 0; i < M; i++) {
int a, b, l;
cin >> a >> b >> l;
--a, --b;
graph[a].push_back((edge){b, l});
graph[b].push_back((edge){a, l});
}
Dijkstra();
int ret = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < graph[i].size(); j++) {
const edge& e = graph[i][j];
int U = i, V = e.to;
if(min_cost[U] > min_cost[V]) swap(U, V);
if(min_cost[U] + e.cost != min_cost[V]) {
ret = max(ret, (min_cost[U] + min_cost[V] + e.cost + 1) / 2);
} else {
ret = max(ret, min_cost[V]);
}
}
}
cout << ret << endl;
}

ステータス

項目 データ
問題 0002 - JOI 国の買い物事情 (Shopping in JOI Kingdom)
ユーザー名 ei1333
投稿日時 2015-12-22 14:48:17
言語 C++11
状態 Accepted
得点 100
ソースコード長 1401 Byte
最大実行時間 81 ms
最大メモリ使用量 3660 KB

セット

セット 得点 Cases
1 Subtask1 10 / 10 01-*
2 Subtask2 10 / 10 02-*
3 Subtask3 10 / 10 03-*
4 Subtask4 10 / 10 04-*
5 Subtask5 10 / 10 05-*
6 Subtask6 10 / 10 06-*
7 Subtask7 10 / 10 07-*
8 Subtask8 10 / 10 08-*
9 Subtask9 10 / 10 09-*
10 Subtask10 10 / 10 10-*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-1.in AC 25 ms 476 KB
1
01-2.in AC 21 ms 632 KB
1
01-3.in AC 17 ms 628 KB
1
02-1.in AC 22 ms 876 KB
2
02-2.in AC 24 ms 748 KB
2
03-1.in AC 77 ms 2808 KB
3
03-2.in AC 76 ms 2788 KB
3
04-1.in AC 73 ms 2760 KB
4
04-2.in AC 75 ms 2868 KB
4
05-1.in AC 73 ms 2028 KB
5
05-2.in AC 73 ms 2048 KB
5
05-3.in AC 66 ms 2180 KB
5
06-1.in AC 64 ms 2036 KB
6
06-2.in AC 70 ms 2052 KB
6
06-3.in AC 71 ms 2196 KB
6
07-1.in AC 69 ms 2692 KB
7
07-2.in AC 71 ms 2736 KB
7
08-1.in AC 72 ms 3552 KB
8
08-2.in AC 81 ms 3368 KB
8
09-1.in AC 71 ms 3072 KB
9
09-2.in AC 70 ms 3048 KB
9
09-3.in AC 73 ms 2848 KB
9
10-1.in AC 72 ms 3520 KB
10
10-2.in AC 73 ms 3604 KB
10
10-3.in AC 73 ms 3660 KB
10