Submission #00019

ソースコード

?
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
#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];
long long mem[3005][3005]={0};
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(d,b));
edge[b].to.push_back(Pii(d,a));
}
for(int i=1;i<=n;i++){
edge[i].min=LLINF;
}
for(int i=0;i<k;i++){
cin>>c;
que.push(Pii(0,c));
while(!que.empty()){
long long nowc=que.top().F;
int nowp=que.top().S;
que.pop();
for(int i=0;i<edge[nowp].to.size();i++){
long long nextc=edge[nowp].to[i].F;
long long nextp=edge[nowp].to[i].S;
long long nextmin=edge[nextp].min;
if(nextmin>nowc+nextc){
edge[nextp].min=nowc+nextc;
mem[nowp][nextp]=mem[nextp][nowp]=nowc+(nextc/2+nextc%2);
que.push(Pii(nowc+nextc,nextp));
}
}
}
}
long long ans=0;
for(long long i=1;i<=n;i++){
for(long long j=1;j<=n;j++){
ans=max(ans,mem[i][j]);
}
}
cout<<ans<<endl;
}

ステータス

項目 データ
問題 0002 - JOI 国の買い物事情 (Shopping in JOI Kingdom)
ユーザー名 ei1417
投稿日時 2015-12-22 14:13:33
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 1230 Byte
最大実行時間 1000 ms
最大メモリ使用量 65536 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-1.in WA 15 ms 604 KB
1
01-2.in WA 20 ms 3260 KB
1
01-3.in WA 16 ms 3204 KB
1
02-1.in WA 34 ms 11864 KB
2
02-2.in WA 24 ms 11732 KB
2
03-1.in WA 83 ms 50384 KB
3
03-2.in WA 84 ms 50520 KB
3
04-1.in WA 87 ms 50432 KB
4
04-2.in WA 86 ms 50700 KB
4
05-1.in MLE 902 ms 65536 KB
5
05-2.in MLE 1000 ms 65536 KB
5
05-3.in MLE 1000 ms 65536 KB
5
06-1.in MLE 947 ms 65536 KB
6
06-2.in MLE 792 ms 65536 KB
6
06-3.in MLE 844 ms 65536 KB
6
07-1.in WA 70 ms 27756 KB
7
07-2.in WA 70 ms 27864 KB
7
08-1.in MLE 498 ms 65536 KB
8
08-2.in MLE 724 ms 65536 KB
8
09-1.in MLE 758 ms 65536 KB
9
09-2.in MLE 660 ms 65536 KB
9
09-3.in WA 90 ms 51572 KB
9
10-1.in MLE 624 ms 65536 KB
10
10-2.in MLE 761 ms 65536 KB
10
10-3.in MLE 1000 ms 65536 KB
10