本番で「スパイダー人」というシュールな単語に戦意を喪失させられたアレ。当然時間内では解けなかったっていうか、そもそもそっちまで時間が回らなかった。
単純な制約付き最短経路問題→ダイクストラのアルゴリズムで解ける!とのことだからやってみた。未確定の頂点コストを更新する部分で、「50メートル以内」っていう条件が登場するのがポイント。じっくりやれば解けないことはないけど、限られた時間でコードディングするのは難しそうだなー。早くC++を習得して、STLの能力を活用したいところ。
#include <stdio.h> #include <math.h> typedef struct { int id, x, y, done, from; double cost; } t_point; t_point point[100]; int start[100], goal[100]; int np, ns; // idから位置を取得 int get_index(int id) { int i; for (i = 0; i < np; i++) { if (id == point[i].id) return i; } return -1; } // データセット入力 int input(void) { int i, s, g; scanf("%d", &np); if (np == 0) return 0; for (i = 0; i < np; i++) { scanf("%d%d%d", &point[i].id, &point[i].x, &point[i].y); } scanf("%d", &ns); for (i = 0; i < ns; i++) { scanf("%d%d", &s, &g); start[i] = get_index(s); goal[i] = get_index(g); } return 1; } // 2点間のコスト double get_cost(t_point start, t_point goal) { int dx = start.x - goal.x, dy = start.y - goal.y; return sqrt(dx*dx + dy*dy); } // ダイクストラ void solve(int start) { int i, done; double cost; // 初期化 for (i = 0; i < np; i++) { point[i].done = 0; point[i].cost = point[i].from = -1; } point[start].cost = 0; for (;;) { // 確定する頂点を選択 done = -1; for (i = 0; i < np; i++) { if (point[i].done || point[i].cost < 0) continue; if (done < 0 || point[i].cost < point[done].cost) { done = i; } } // 確定する頂点がなければ終了 if (done < 0) break; point[done].done = 1; // 未確定の頂点コストを更新 for (i = 0; i < np; i++) { cost = get_cost(point[done], point[i]); if (point[i].done || cost > 50.0) continue; if (point[i].cost < 0 || point[done].cost + cost < point[i].cost) { point[i].cost = point[done].cost + cost; point[i].from = done; } } } } // 最短経路を出力 void output(int goal) { int i; int result[100]; // ゴールのコストが不明 => NA if (point[goal].cost < 0) { puts("NA"); return; } // resultに経路をゴールから格納 for (i = 0; goal >= 0; i++) { result[i] = point[goal].id; goal = point[goal].from; } // resultを逆順に表示 for (i = i-1; i >= 0; i--) { printf("%d ", result[i]); } printf("\n"); } int main(void) { int i; while (input()) { for (i = 0; i < ns; i++) { solve(start[i]); output(goal[i]); } } return 0; }
Algorithm Noteさんとこにあったwhile (input())
のやりかたが頭良すぎると思ったのでパクらせていただいた。うん、データセットで入力する問題はこれからこの方式で解こう。つーかブログに貼り付けるにはこのコード長すぎるよね。