Submission #00025

ソースコード

?
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
#include<bits/stdc++.h>
#define INF (1<<29)
#define LLINF (1LL<<59)
#define F first
#define S second
using namespace std;
typedef pair<long long,long long> Pii;
typedef struct{
vector<Pii> to;
long long min;
}Edge;
Edge edge[3005];
bool check[3005];
int n,m,k;
priority_queue<Pii,vector<Pii>,greater<Pii> > que;
main(){
cin>>n>>m>>k;
int a,b,c,d;
for(int i=0;i<m;i++){
cin>>a>>b>>d;
edge[a].to.push_back(Pii(b,d));
edge[b].to.push_back(Pii(a,d));
}
for(int i=1;i<=n;i++){
edge[i].min=LLINF;
}
for(int i=0;i<k;i++){
cin>>c;
edge[c].min=0;
memset(check,0,sizeof(check));
que.push(Pii(0,c));
while(!que.empty()){
long long nowc=que.top().F;
long long nowp=que.top().S;
que.pop();
check[nowp]=true;
for(int i=0;i<edge[nowp].to.size();i++){
long long nextc=edge[nowp].to[i].S;
long long nextp=edge[nowp].to[i].F;
long long nextmin=edge[nextp].min;
if(check[nextp]==false&&nextmin>nowc+nextc){
edge[nextp].min=nowc+nextc;
que.push(Pii(nowc+nextc,nextp));
}
}
}
}
long long ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<edge[i].to.size();j++){
long long nextp=edge[i].to[j].F;
long long nextc=edge[i].to[j].S;
ans=max(ans,(edge[i].min+edge[nextp].min+nextc)/2+(edge[i].min+edge[nextp].min+nextc)%2);
}
}
cout<<ans<<endl;
}

ステータス

項目 データ
問題 0002 - JOI 国の買い物事情 (Shopping in JOI Kingdom)
ユーザー名 ei1417
投稿日時 2015-12-22 14:45:39
言語 C++11
状態 Accepted
得点 100
ソースコード長 1412 Byte
最大実行時間 531 ms
最大メモリ使用量 6464 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 22 ms 604 KB
1
01-2.in AC 20 ms 476 KB
1
01-3.in AC 25 ms 556 KB
1
02-1.in AC 22 ms 1140 KB
2
02-2.in AC 21 ms 1124 KB
2
03-1.in AC 71 ms 4964 KB
3
03-2.in AC 76 ms 5092 KB
3
04-1.in AC 79 ms 5160 KB
4
04-2.in AC 76 ms 5012 KB
4
05-1.in AC 73 ms 3656 KB
5
05-2.in AC 189 ms 3556 KB
5
05-3.in AC 531 ms 3848 KB
5
06-1.in AC 70 ms 3612 KB
6
06-2.in AC 70 ms 3644 KB
6
06-3.in AC 64 ms 3808 KB
6
07-1.in AC 70 ms 4836 KB
7
07-2.in AC 71 ms 4816 KB
7
08-1.in AC 76 ms 6416 KB
8
08-2.in AC 77 ms 6356 KB
8
09-1.in AC 70 ms 5428 KB
9
09-2.in AC 76 ms 5588 KB
9
09-3.in AC 76 ms 5108 KB
9
10-1.in AC 78 ms 6232 KB
10
10-2.in AC 78 ms 6464 KB
10
10-3.in AC 80 ms 6412 KB
10