FLYING

/* TODO: 気の利いた説明を書く */

パソコン甲子園2007予選問題 問08

本番で「スパイダー人」というシュールな単語に戦意を喪失させられたアレ。当然時間内では解けなかったっていうか、そもそもそっちまで時間が回らなかった。

単純な制約付き最短経路問題→ダイクストラアルゴリズムで解ける!とのことだからやってみた。未確定の頂点コストを更新する部分で、「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())のやりかたが頭良すぎると思ったのでパクらせていただいた。うん、データセットで入力する問題はこれからこの方式で解こう。つーかブログに貼り付けるにはこのコード長すぎるよね。