読者です 読者をやめる 読者になる 読者になる

FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

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

c/c++ memo

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

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