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; }