Aizu Online Judge 0526 - Boat Travel

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526

日本語.

解法

クエリごとにDijkstraするだけ.

ソースコード

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct edge {
    int to, cost;
};

typedef pair<int, int> P;

const int INF = 1e7;

vector<edge> graph[110];
int cost[110];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > Q;
    fill((int* )cost, (int* )(cost + 110), INF);

    Q.push(P(0, s));
    cost[s] = 0;
    while (!Q.empty()) {
        P p = Q.top(); Q.pop();
        if (cost[p.second] < p.first) continue;

        for (int i = 0; i < graph[p.second].size(); i++) {
            edge e = graph[p.second][i];
            if (cost[e.to] > p.first + e.cost) {
                Q.push(P(p.first + e.cost, e.to));
                cost[e.to] = p.first + e.cost;
            }
        }
    }
}

int main() {
    int n, k;
    while (cin >> n >> k, n | k) {
        for (int i = 0; i < n; i++) graph[i].clear();

        for (int i = 0; i < k; i++) {
            int o, a, b, c, d, e;
            cin >> o;
            if (o == 0) {
                cin >> a >> b;
                dijkstra(a - 1);
                if (cost[b - 1] < INF) cout << cost[b - 1] << endl;
                else cout << -1 << endl;
            } else {
                cin >> c >> d >> e;
                graph[c - 1].push_back((edge){d - 1, e});
                graph[d - 1].push_back((edge){c - 1, e});
            }
        }
    }

    return 0;
}

感想

Dijkstra法を書くのも慣れてきました.