ABC 012 D

本日最後の問題はこれです。

abc012.contest.atcoder.jp

n地点とm本のバスの情報が与えられます。バスはa地点とb地点を時間tかけて移動します。バスはそれぞれその区間を往復し、行きも帰りも同じ時間かかり、好きな時間に乗ることができる(=バス同士ののりつぎの時間は考えなくてよい)とします。i地点を出発点として、出発点以外の場所へ移動するのにかかる最大の時間をT(i)としたとき、min(T(i))を求めなさい、という問題です。ちょっと問題文がややこしかった。

nも300と多くないのでそれぞれの地点についてダイクストラ法でT(i)を求め、その最小値を答えとしました。
解答はこんな感じです。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    int n;
    int conection[301][301] = {};
     
    int dijkstra(int i)
    {
        priority_queue<pair<int, int> > qu;
        vector<bool> ischecked(n + 1, false);
        qu.push(make_pair(0, i));
        int checkedplacenum = 1;
        // cout << i << endl;
        while(!qu.empty()){
            int nowtime = (qu.top()).first;
            int nowplace = (qu.top()).second;
            // cout << -nowtime << " " << nowplace << endl;
            qu.pop();
            if(ischecked[nowplace]) continue;
            ischecked[nowplace] = true;
            checkedplacenum++;
            if(checkedplacenum == n + 1) return -nowtime;
            for(int j = 1; j <= n; j++){
                if(!ischecked[j] && conection[nowplace][j] != 0){
                    qu.push(make_pair(nowtime + conection[nowplace][j], j));
                }
            }
        }
        return mod;
    }
     
     
    int main()
    {
        int m;
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            int a, b, t;
            cin >> a >> b >> t;
            conection[a][b] = -t;
            conection[b][a] = -t;
        }
        int ans = mod;
        for(int i = 1; i <= n; i++){
            ans = min(ans, dijkstra(i));
        }
        cout << ans << endl;
    }

接続行列でtを-tにしているのは、ダイクストラ法で扱いやすくするためです。tの最小値がキューのトップに出てきてほしいのですが、優先度つきキューでは最大値がトップに出てきてしまうのでこうしました。すべての地点に対してチェックが完了した時がT(i)となります。あとはmain関数内で結果を比較すればいいだけです。