2387:Til the Cows Come Home

keyword

dijkstra　無向グラフ　C++

概要

長さ付きの無向辺が与えられる。ノードNからノード1への最短路を求める問題。
純粋なdijkstraの問題。ここぞとばかりにライブラリの実験をしてみた。一応無事AC。ちなみに同じノード間を繋ぐが長さが違う辺もあるらしく、見事に引っかかってしまった。

#define INF (1<<28)

vector<int> dijkstra(vector< vector<int> > graph, int s){
    int n = (int)graph.size();
    vector<int> dist(n,INF);
    priority_queue<pair<int, int>,vector< pair<int, int> >, greater< pair<int, int> > > Q;

    dist[s] = 0;
    Q.push(make_pair(0,s));

    while(!Q.empty()){
        pair<int, int> top = Q.top();
        Q.pop();

        int v = top.second, d = top.first;
        if(d <= dist[v]){
            for(int v2=0; v2<n; v2++){
                if(dist[v2] > dist[v] + graph[v][v2]){
                    dist[v2] = dist[v] + graph[v][v2];
                    Q.push(make_pair(dist[v2], v2));
                }
            }
        }
    }
    return dist;
}

int main(){
    int t, n, i, a, b, c;
    scanf("%d%d",&t,&n);
    vector< vector<int> > graph(n, vector<int>(n,INF));
    REP(i,t){
        scanf("%d%d%d",&a,&b,&c);
        graph[a-1][b-1] = graph[b-1][a-1] = min(graph[a-1][b-1], c);
    }
    vector<int> dist = dijkstra(graph, n-1);

    printf("%d\n", dist[0]);
    return 0;
}