2085-Turn Left

問題概要

直進か左側に曲がることしか出来ない運転手が移動することになった．
最短の距離で移動した時の最小の交差点を通る回数を求めよ．

実装

ダイクストラ法

解法(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <complex>
#include <queue>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)


const double EPS=1e-7;
typedef complex<double> Point;
inline double cross(const Point &a,const Point &b){return imag(conj(a)*b);}
inline double dot(const Point &a,const Point &b){return real(conj(a)*b);}
typedef complex<double> Point;
int ccw(Point a,Point b,Point c){
    b-=a;c-=a;
    if(cross(b, c)>0)return +1;       // counter clockwise
    if(cross(b, c)<0)return -1;       // clockwise
    if(dot(b, c)<0)return +2;       // c--a--b on line
    if(norm(b)<norm(c))return -2;       // a--b--c on line
    return 0;
}

typedef double Weight;
struct Edge{
	int src,dst;
	Weight cost;
	Edge(int f,int t,int c=0){src=f;dst=t;cost=c;}
};
struct Node:public vector<Edge>{
	int x,y;
	string name;
};

bool operator<(const Edge &a,const Edge &b){
	return a.cost!=b.cost?a.cost<b.cost:a.dst==b.dst?a.src<b.src:a.dst<b.dst;
}
bool operator>(const Edge &a,const Edge &b){return b<a;}
struct State{
	int first,second;
	double dist;
	int cnt;
};
bool operator<(const State &a,const State &b){
	if(abs(a.dist-b.dist)<EPS)return a.cnt<b.cnt;
	return a.dist<b.dist;
}
bool operator>(const State &a,const State &b){return b<a;}
typedef vector<Node> Graph;
typedef pair<int,int> P;
typedef pair<double,int> Q;
int solve(Graph &G,int s,int e){
	map<P,Q> dist;
	priority_queue<State,vector<State>,greater<State> > que;
	REP(i,G[s].size()){
		que.push((State){s,G[s][i].dst,G[s][i].cost,2});
		dist[P(s,G[s][i].dst)]=Q(G[s][i].cost,2);
	}
	while(!que.empty()){
		State now=que.top();que.pop();
		if(now.second==e){
			return dist[P(now.first,now.second)].second;
		}
		REP(i,G[now.second].size()){
			int next=G[now.second][i].dst;
			int C=ccw(Point(G[now.first].x,G[now.first].y),Point(G[now.second].x,G[now.second].y),Point(G[next].x,G[next].y));
			if(C==1||C==-2){
				if(dist.find(P(now.second,next))==dist.end()||dist[P(now.second,next)]>Q(now.dist+G[now.second][i].cost,now.cnt+1)){
					dist[P(now.second,next)]=Q(now.dist+G[now.second][i].cost,now.cnt+1);
					que.push((State){now.second,next,dist[P(now.second,next)].first,dist[P(now.second,next)].second});
				}
			}
		}
	}
	return -1;
}
int main(){
	int m,n;
	for(;cin>>m>>n;){
		if(m==0&&n==0)break;
		map<string,int> vec2int;
		Graph G(m);
		REP(i,m){
			cin>>G[i].name>>G[i].x>>G[i].y;
			vec2int[G[i].name]=i;
		}
		REP(i,n){
			string a_,b_;
			cin>>a_>>b_;
			int a=vec2int[a_],b=vec2int[b_];
			G[a].push_back(Edge(a,b,hypot(G[a].x-G[b].x,G[a].y-G[b].y)));
			G[b].push_back(Edge(b,a,hypot(G[a].x-G[b].x,G[a].y-G[b].y)));
		}
		string s_,e_;int s,e;
		cin>>s_>>e_;
		s=vec2int[s_];
		e=vec2int[e_];
		int res=solve(G,s,e);
		if(res==-1){
			cout<<"impossible"<<endl;
		}else{
			cout<<res<<endl;
		}
	}
}