Submission #00036

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int e[1111][1111],d[1111][1111];
signed main(){
int n,m,s,g;
cin>>n>>m>>s>>g;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
e[i][j]=d[i][j]=(1LL<<50LL);
for(int i=0;i<n;i++) e[i][i]=d[i][i]=0;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
d[a][b]=d[b][a]=e[a][b]=e[b][a]=min(e[a][b],c);
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
/*//
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cout<<e[i][j]<<" \n"[j==n-1];
//*/
int p=s;
while(p!=g){
if(p!=s) cout<<" ";
cout<<p;
for(int i=0;i<n;i++){
if(i!=p&&d[p][i]+e[i][g]==e[p][g]){
p=i;
break;
}
}
}
cout<<" "<<g<<endl;
return 0;
}

ステータス

項目 データ
問題 0005 - スニーカーマン
ユーザー名 beet
投稿日時 2017-01-29 19:21:09
言語 C++11
状態 Accepted
得点 200
ソースコード長 866 Byte
最大実行時間 34 ms
最大メモリ使用量 5768 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
10_random_a_1_in.txt AC 34 ms 5600 KB
1
10_random_a_3_in.txt AC 32 ms 5632 KB
1
20_random_b_02_in.txt AC 28 ms 5536 KB
1
20_random_b_04_in.txt AC 21 ms 5572 KB
1
20_random_b_06_in.txt AC 31 ms 5608 KB
1
20_random_b_08_in.txt AC 28 ms 5640 KB
1
20_random_b_10_in.txt AC 20 ms 5676 KB
1
20_random_b_12_in.txt AC 29 ms 5708 KB
1
20_random_b_14_in.txt AC 22 ms 5736 KB
1
20_random_b_16_in.txt AC 33 ms 5768 KB
1
20_random_b_18_in.txt AC 25 ms 5668 KB
1
20_random_b_20_in.txt AC 25 ms 5704 KB
1
30_special_1_in.txt AC 30 ms 5604 KB
1
30_special_2_in.txt AC 30 ms 5636 KB
1
30_special_3_in.txt AC 26 ms 5672 KB
1