D - バスと避けられない運命

時間制限 : 5sec / メモリ制限 : 256MB

問題文

高橋君は、バスがあまり好きではありません。ですが、社会に出ると、バスを乗るという行為を避けることはできません。

社会人になると、自宅から会社まで、バスで通わなければなりません。高橋君はまだ内定を貰っていないので、会社の場所は解りません。

高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。

追記：なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。

各バスは、2 つのバス停を往復するように走っており、行き・帰りでかかる時間に差はありません。バスにはいつでも乗ることが可能であり、乗継にかかる時間などは無視することが可能です。

また、自宅や会社はバス停に隣接しており、他のバス停まで歩いたり、バス以外の手段で移動することはできません。

高橋君が引っ越すべき場所を求め、そこに引っ越した際の、バスに乗らなければならない時間の最大値を出力してください。

note

nが 300と小さいので　普通のダイクストラn回のO(n3)でもとける。けど俺時にはプライオリティーキーつかったダイクストラの方が楽だからそっちで実装。ワーシャルフロイトでもO(n3)でとける

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define ll long long
#define P pair<ll, ll>

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

using namespace std;

const ll MAX = 1e9+7;

struct Edge
{
    int to;
    int cost;
};

ll dijkstra(const vector<Edge> G[], int n, int start){
    priority_queue<P, vector<P>, greater<P> > que; //P　first is cost, second is index
    vector<ll> dis(n, MAX);
    dis[start] = 0;
    // vector<int> check(n, 1); // 未訪問が1
    // check[start] = 0;
    que.push(P(0, start) );

    while(!que.empty()){
        P cur = que.top();
        que.pop();
        // que にはindexが重複するものがあるため
        if(cur.first > dis[cur.second]) continue;
        for (int i = 0; i < G[cur.second].size() ; ++i)
        {
            Edge next = G[cur.second][i];
            if(dis[cur.second] + next.cost < dis[next.to] ){
                dis[next.to] = dis[cur.second] + next.cost; 
                que.push(P(dis[next.to], next.to) );
            }
        }
    }
    sort(dis.begin(), dis.end());
    return dis[n-1];
}

int main(){
    int n, m;
    vector<Edge> G[301];

    cin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        int a, b, t;
        cin >> a >> b >> t;
        a--;
        b--;
        Edge e1 = {b, t};
        Edge e2 = {a, t}; 
        G[a].push_back(e1);
        G[b].push_back(e2);
    }

    ll ans = MAX;

    for (int i = 0; i < n; ++i)
    {
        ans = min(ans, dijkstra(G, n, i) ); 
    }

    cout << ans << endl;

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 012 #27

D - バスと避けられない運命

問題文

note