AOJ_0526 Boat Travel

問題
解法
ダイクストラ法で解いた。
うろ覚えで書いて正直通ると思っていなかったのに、通ってうれしい。

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int ,int> P; //first 距離  second 位置
const int MAX_N = 100, INF = 1 << 30;
int G[MAX_N][MAX_N]; //グラフ
int N, K;

// うろ覚えダイクストラ法
int dijk(int s, int g){
	priority_queue<P, vector<P>, greater<P> > Q;
	int d[MAX_N]; //最短距離を入れる配列
	fill(d, d + MAX_N, INF); //INFで初期化
	Q.push(P(0, s));
	//ダイクストラ スタート!
	while(!Q.empty()){
		P p = Q.top(); Q.pop();
		int pd = p.first, pp = p.second;

		if(pd >= d[pp]) continue;

		d[pp] = pd; //最短距離を更新
		for(int i = 0; i < N; i++){
			if(G[pp][i] == INF) continue;
			Q.push(P(pd + G[pp][i], i));
		}
	}
	return d[g];
}
int main(){
	while(scanf("%d %d", &N, &K) && N){
		for(int i = 0; i < MAX_N; i++)
			for(int j = 0; j < MAX_N; j++)
				G[i][j] = INF; //初期化
		for(int i = 0; i < K; i++){
			int t, a, b, cost;
			scanf("%d %d %d", &t, &a, &b);
			--a; --b;
			if(t == 0){
				//客の注文
				int ans = dijk(a,b);
				printf("%d\n", (ans==INF) ? -1 : ans);
			}else{
				//新しい航路情報
				scanf("%d", &cost);
				//今までのと、新しいのはどっちが安いか
				if(G[a][b] > cost){ //新しいほうに更新
					G[a][b] = cost; G[b][a] = cost;
				}
			}
		}
	}
	return 0;
}