Submission #1587158

---

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

const int INF = 1e9-1;

////////////////////////////////////////
//AtCoder Beginner Contest 012
//D - バスと避けられない運命
//
//最短経路問題
//
////////////////////////////////////////

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(i,1,N+1) {
        rep(j,1,N+1) {
            rep(k,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

Judge Result