Submission #1587808
Source Code Expand
#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <unordered_map> //ハッシュ関数
using namespace std;
//デバッグ時はTESTを定義する。本番時はこの行をコメントアウトする
//#define TEST //*******************************************************************************************************************************************
//そうすることで、以下に定義する、デバッグ時にのみ標準出力する、doutコマンドが実現できる。本番時はダミーストリームに出力
#ifdef TEST
#define dout cout
#else
stringstream dummy; //デバッグ時のdoutコマンドのダミー出力先
#define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummyを毎回リセットしておかないとメモリ溢れちゃう。
//どうせ表示しないからgoodbitしなくていいけど、表示する場合はこれしておかないとバグるらしいので、勉強のために。詳しくは http://d.hatena.ne.jp/linden/20060427/p1
#endif
#define disp(A) dout << #A << " = " << (A) << endl
#define disP(A) dout << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
////////////////////////////////////////
//AIZU
//Convenient Location
//
//最短経路問題
//
//WAでだめ。例題はクリアできたのに。
//サンプルinputが非公開のためお手上げ。
////////////////////////////////////////
//
//const int INF = 1e9-1;
//
//int main(void) {
//
// int N = 10; //頂点数は最大でも10
// int M; //辺数
// int a, b, c;
//
// unsigned long long d[N][N]; //0~9の添字を使う
// unsigned long long sumTotalCost[N]; //sumTotalCost[i] = i出発で、他の任意の頂点への最短距離の総和を保存。この中の最小値がansとなる
//
//
// while(1) {
// cin >> M;
// if( M== 0 ) break;
//
// //initialization
// rep(i,0,N) {
// rep(j,0,N) {
// d[i][j] = (i==j ? 0 : INF);
// }
// }
//
// rep(i,0,N) {
// sumTotalCost[i] = 0;
// }
//
//
// rep(i,0,M) {
// cin >> a >> b >> c; //頂点aからbまでのコストt
//
// d[a][b] = d[b][a] = c;
// }
//
// //test display
// rep(i,0,N) {
// disP(i);
// dispAll(d[i], N);
// }
// dout << endl;
//
// //Warshall Floyd Algorithm
// rep(i,0,N) {
// rep(j,0,N) {
// rep(k,0,N) {
// d[i][j] = min( d[i][j], d[i][k] + d[k][j] );
// }
// }
// }
//
// //test display
// rep(i,0,N) {
// disP(i);
// dispAll(d[i], N);
// }
// dout << endl;
//
//
// //各頂点について通勤時間の総和を求める
// rep(i,0,N) {
// rep(j,0,N) {
// sumTotalCost[i] += ( d[i][j]==INF ? 0 : d[i][j] ); //INFは無視してINF以外の数字を足し上げる
// }
// }
//
// //test display
// dispAll(sumTotalCost, N);
// dout << endl;
//
//
// //通勤時間の総和が最小となる町を求める
// int ans = INF;
// int ans_Origin = 0;
// rep(i,0,N) {
// if( ans > sumTotalCost[i] && sumTotalCost[i] != 0 ) { //町が存在してないiはsumTotalが0なので、0の項は無視する
// ans = sumTotalCost[i];
// ans_Origin = i;
// }
// }
//
// disp(ans_Origin);
// dout << "に住んだとき、通勤時間の総和が最小となる。その通勤時間の総和は\n";
// disp(ans);
// dout << "となる。\n";
//
// cout << ans_Origin << " " << ans << endl;
//
// }
//
// return 0;
//}
////////////////////////////////////////
//AtCoder Beginner Contest 012
//D - バスと避けられない運命
//
//最短経路問題
//こちらも一部WAというかほとんどWA。。。なんでだ!?
//http://abc012.contest.atcoder.jp/submissions/1587158
////////////////////////////////////////
//
const int INF = 1e9-1;
int main(void) {
int N; //頂点数
int M; //辺数
int a, b, t;
cin >> N >> M;
int d[N+1][N+1]; //1~Nの添字を使う。0は使わない
int worstCase[N+1][2]; //各頂点出発で、他の任意の頂点への最短距離の中の最大値(ワーストケース)を[0]に、そのワーストとなる行き先を[1]に保存。こちらも添字0は使わない。このワーストケースの中の最小値がansとなる
//initialization
rep(i,0,N+1) {
rep(j,0,N+1) {
d[i][j] = (i==j ? 0 : INF);
}
}
rep(i,0,N+1) {
worstCase[i][0] = worstCase[i][1] = INF;
}
rep(i,0,M) {
cin >> a >> b >> t; //頂点aからbまでのコストt
d[a][b] = d[b][a] = t;
}
//test display
rep(i,0,N+1) {
disP(i);
dispAll(d[i], N+1);
}
dout << endl;
//Warshall Floyd Algorithm
rep(k,1,N+1) {
rep(i,1,N+1) {
rep(j,1,N+1) {
d[i][j] = min( d[i][j], d[i][k] + d[k][j] );
}
}
}
//test display
rep(i,0,N+1) {
disP(i);
dispAll(d[i], N+1);
}
dout << endl;
//各頂点に住んだとき、すなわち各行d[i][]のそれぞれ最大値=ワーストケースを求める
int worstTime;
int worstDistination;
rep(i,1,N+1) {
worstTime = 0;
worstDistination = 0;
rep(j,1,N+1) {
if( worstTime < d[i][j] ) {
worstTime = d[i][j];
worstDistination = j;
}
}
worstCase[i][0] = worstTime;
worstCase[i][1] = worstDistination;
}
//test display
rep(i,0,N+1) {
disP(i);
dispAll(worstCase[i], 2);
}
dout << endl;
//ワーストケースの中の一番マシな値(最小値)を求める
int ans = INF;
int ans_worstOrigin = 0; //これは要らないんだけど参考までに
int ans_worstDistination = 0; //これは要らないんだけど参考までに
rep(i,1,N+1) {
if( ans > worstCase[i][0] ) {
ans = worstCase[i][0];
ans_worstDistination = worstCase[i][1];
ans_worstOrigin = i;
}
}
disp(ans_worstOrigin);
dout << "に住んだとき、最悪のケースでも通勤時間が最小となる。その最悪のケースは\n";
disp(ans_worstDistination);
dout << "へ向かうケースで、そのときの所要時間は\n";
disp(ans);
dout << "となる。\n";
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - バスと避けられない運命 |
User |
manu_gino |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
7600 Byte |
Status |
AC |
Exec Time |
74 ms |
Memory |
640 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
test_01.txt |
AC |
1 ms |
256 KB |
test_02.txt |
AC |
47 ms |
640 KB |
test_03.txt |
AC |
74 ms |
640 KB |
test_04.txt |
AC |
20 ms |
384 KB |
test_05.txt |
AC |
28 ms |
384 KB |
test_06.txt |
AC |
5 ms |
256 KB |
test_07.txt |
AC |
57 ms |
512 KB |
test_08.txt |
AC |
2 ms |
256 KB |
test_09.txt |
AC |
21 ms |
384 KB |
test_10.txt |
AC |
5 ms |
256 KB |
test_11.txt |
AC |
5 ms |
256 KB |
test_12.txt |
AC |
29 ms |
512 KB |
test_13.txt |
AC |
5 ms |
256 KB |
test_14.txt |
AC |
7 ms |
256 KB |
test_15.txt |
AC |
53 ms |
512 KB |
test_16.txt |
AC |
8 ms |
256 KB |
test_17.txt |
AC |
23 ms |
384 KB |
test_18.txt |
AC |
27 ms |
384 KB |
test_19.txt |
AC |
9 ms |
256 KB |
test_20.txt |
AC |
7 ms |
256 KB |
test_21.txt |
AC |
1 ms |
256 KB |
test_22.txt |
AC |
13 ms |
384 KB |
test_23.txt |
AC |
1 ms |
256 KB |
test_24.txt |
AC |
47 ms |
640 KB |
test_25.txt |
AC |
47 ms |
640 KB |
test_26.txt |
AC |
14 ms |
384 KB |
test_27.txt |
AC |
17 ms |
384 KB |
test_28.txt |
AC |
49 ms |
640 KB |
test_29.txt |
AC |
48 ms |
640 KB |
test_30.txt |
AC |
5 ms |
256 KB |
test_31.txt |
AC |
2 ms |
256 KB |
test_32.txt |
AC |
48 ms |
640 KB |
test_33.txt |
AC |
48 ms |
640 KB |
test_34.txt |
AC |
3 ms |
256 KB |
test_35.txt |
AC |
11 ms |
384 KB |
test_36.txt |
AC |
48 ms |
640 KB |