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
AC × 39
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