Language: C++

/*
02:08 - 04:05
 */

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<queue>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 2000
#define pow2(a) ((a)*(a))
#define EPS 1e-7
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

struct Point{
  double x,y;
  Point(double x=IINF,double y=IINF):x(x),y(y){}
  Point operator - (const Point& a)const { return {x-a.x,y-a.y}; }
};

struct Edge{
  int from,to;
  double dist;
  Edge(int from=IINF,int to=IINF,double dist=IINF):from(from),to(to),dist(dist){}
};

struct Data{
  int pre,cur,cost;
  double dist;
  Data(int pre=IINF,int cur=IINF,int cost=IINF,double dist=IINF):pre(pre),cur(cur),cost(cost),dist(dist){}
  bool operator < (const Data& a) const {
    if(equals(dist,a.dist))return cost > a.cost;
    return dist > a.dist;
  }
};

inline double getDist(Point a,Point b){ return sqrt(pow2(a.x-b.x)+pow2(a.y-b.y)); }
inline double cross(Point a,Point b){ return a.x*b.y-a.y*b.x; }

vector<Edge> G[MAX];
vector<Point> ps;
double mindist[MAX][MAX];//mindist[pre_node][cur_node] 
int    mincost[MAX][MAX];
int E,V,sp,gp;

void compute(){

  rep(i,V)rep(j,V){
    mindist[i][j] = IINF;
    mincost[i][j] = IINF;
  }
  priority_queue<Data> Q;
  rep(i,G[sp].size()){
    mindist[sp][G[sp][i].to] = G[sp][i].dist;
    mincost[sp][G[sp][i].to] = 2;
    Q.push(Data(sp,G[sp][i].to,2,G[sp][i].dist));
  }

  while(!Q.empty()){
    Data data = Q.top(); Q.pop();
    Point cp = ps[data.cur];
    Point pp = ps[data.pre];

    if(data.cur == gp){ cout << data.cost << endl; return; }

    rep(i,G[data.cur].size()){
      int next = i;
      Point np = ps[G[data.cur][next].to];
      if(G[data.cur][next].to == data.pre)continue;
      if(cross(cp-pp,np-pp) < -EPS)continue;
      double dist = G[data.cur][next].dist;
      if(equals(mindist[data.cur][next],data.dist+dist)){
	if(mincost[data.cur][G[data.cur][next].to] > data.cost+1){
	  mincost[data.cur][G[data.cur][next].to] = data.cost+1;
	  Q.push(Data(data.cur,G[data.cur][next].to,data.cost+1,data.dist+dist));
	}
      } else if(mindist[data.cur][G[data.cur][next].to] > data.dist+dist){
	mindist[data.cur][G[data.cur][next].to] = data.dist + dist;
	mincost[data.cur][G[data.cur][next].to] = data.cost + 1;
	Q.push(Data(data.cur,G[data.cur][next].to,data.cost+1,data.dist+dist));
      }
    }
  }

  cout << "impossible" << endl;

}

int main(){
  while(cin >> V >> E,V|E){
    unordered_map<string,int> getIndex;
    int x,y;
    string name,p,q;
    ps.clear();
    rep(i,V)G[i].clear();

    rep(i,V){
      cin >> name >> x >> y;
      getIndex[name] = (int)ps.size();
      ps.push_back(Point(x,y));
    }
    assert(getIndex.size() == ps.size());

    rep(i,E){
      cin >> p >> q;
      int node1 = getIndex[p], node2 = getIndex[q];
      G[node1].push_back(Edge(node1,node2,getDist(ps[node1],ps[node2])));
      G[node2].push_back(Edge(node2,node1,getDist(ps[node1],ps[node2])));
    }

    cin >> p >> q;
    sp = getIndex[p], gp = getIndex[q];

    compute();

  }
  return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:110:5: error: 'assert' was not declared in this scope
  110 |     assert(getIndex.size() == ps.size());
      |     ^~~~~~
a.cc:12:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
   11 | #include<climits>
  +++ |+#include <cassert>
   12 |