Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2007-day3 Route

問題文 : 象使い(pdf注意, 2-3ページ目)

解法 :
辺と辺で成される角を求めるには, (直前の点, 今いる点, 次に行く点)の3つの情報が必要である.

直前の点をvec(P_0) = (x0, y0), 今いる点をvec(P_1) = (x1, y1), 次に行く点をvec(P_2) = (x2, y2) とすると
(vec(P0) - vec(P1)) ・ (vec(P2) - vec(P1)) ≦ 0であれば, その辺と辺は鋭角ではないため, 通ることが可能である.

上記の点を踏まえ, (直前の点, 今いる点)を状態として持つ最短経路探索を行えば, O(NlogM)時間でこの問題を解くことが出来る.
一度訪れた状態に再び訪れることがないように, 訪問済みの箇所をチェックする配列を用意すると探索が行いやすい.

コード :

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Edge {
	int to;
	int cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
	Edge() {}
};

struct Visit {
	int prev;
	int now;
	int total;
	Visit(int prev, int now, int total) : prev(prev), now(now), total(total) {}
	Visit() {}
};

bool operator < (const Visit &a, const Visit &b)
{
	return (a.total > b.total);
}

vector<Edge> G[100];

int main()
{
	int n, m;
	int x[100], y[100];
	int ans;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++){
		scanf("%d %d", &x[i], &y[i]);
	}
	
	for (int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		a--; b--;
		G[a].push_back(Edge(b, c));
		G[b].push_back(Edge(a, c));
	}
	
	bool done[100][100];
	memset(done, false, sizeof(done));
	
	priority_queue<Visit, vector<Visit> > pque;
	
	pque.push(Visit(0, 0, 0));
	
	while (!pque.empty()){
		Visit t = pque.top();
		pque.pop();
		
		if (done[t.prev][t.now] == true){
			continue;
		}
		done[t.prev][t.now] = true;
		
		if (t.now == 1){
			printf("%d\n", t.total);
			return (0);
		}
		
		for (int i = 0; i < G[t.now].size(); i++){
			int x1 = x[t.prev] - x[t.now], x2 = x[G[t.now][i].to] - x[t.now];
			int y1 = y[t.prev] - y[t.now], y2 = y[G[t.now][i].to] - y[t.now];
			if (x1 * x2 + y1 * y2 <= 0){
				pque.push(Visit(t.now, G[t.now][i].to, t.total + G[t.now][i].cost));
			}
		}
	}
	printf("-1\n");
	return (0);
}