Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"math"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	dd := make([][]int, 1000)
	for i := range dd {
		dd[i] = make([]int, 1000)
	}
	num := make([]int,1000)
	inv := make([]int, 1001)
	x := make([]int, 1000)
	y := make([]int, 1000)
	vv := make([]int, 1000)
	nowt := make([]float64, 1000)
	rev := make([]int, 1000)
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		for i := 0; i < n; i++ {
			scanner.Scan()
			buf1 := strings.Split(scanner.Text(), " ")
			num[i], _ = strconv.Atoi(buf1[0])
			x[i], _ = strconv.Atoi(buf1[1])
			y[i], _ = strconv.Atoi(buf1[2])
			inv[num[i]] = i
		}
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				dd[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])
			}
		}
		scanner.Scan()
		m, _ := strconv.Atoi(scanner.Text())
		for i := 0; i < m; i++ {
			scanner.Scan()
			buf2 := strings.Split(scanner.Text(), " ")
			c, _ := strconv.Atoi(buf2[0])
			d, _ := strconv.Atoi(buf2[1])
			c = inv[c]
			d = inv[d]
			for j := 0; j < n; j++ {
				vv[j] = 0
				nowt[j]=999999999
				rev[j]=-1
			}
			nowt[c]=0
			for j := 0; j < n; j++ {
				M := 99999999
				at := 0
				for k := 0; k < n; k++ {
					if vv[k] == 0 && float64(M) > nowt[k] {
						M=int(nowt[k])
						at = k
					}
				}
				if M > 90000000 {
					break
				}
				vv[at]=1
				for k := 0; k < n; k++ {
					if vv[k] == 0 && dd[at][k]<=2500&&nowt[k]>nowt[at]+math.Sqrt(float64(dd[at][k])) {
						nowt[k]=nowt[at]+math.Sqrt(float64(dd[at][k]))
						rev[k] = at
					}
				}
			}
			if vv[d] == 0 {
				fmt.Println("NA")
			} else {
				stack := make([]int, 0)
				V := d
				for V != c {
					stack = append(stack, V)
					V = rev[V]
				}
				fmt.Print(num[c])
				for len(stack) > 0 {
					fmt.Printf(" %d", num[stack[len(stack)-1]])
					stack = stack[:len(stack)-1]
				}
				fmt.Println()
			}
		}
	}
}

C++: #include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

typedef struct{
  int x;
  int y;
}BILL;
typedef pair<int,int> P;
const int INF = (1<<20);
const int MAX = 1001;
BILL bill[MAX];
int pre[MAX],node[MAX];
int n,m;
vector<int> IN;

void init(){
  fill(pre,pre+MAX, -1);
  fill(node,node+MAX, INF);
}


double Getd(BILL a, BILL b){
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void solve(int from, int to){
  init();
  node[from] = 0;
  priority_queue<P,vector<P>, greater<P> > Q;
  Q.push(P(node[from],from));
  //Q(distance,name)
  while(!Q.empty()){
    P now = Q.top(); Q.pop();
    //   if(now.first > node[now.second]) continue;
    for(int i = 0; i < IN.size(); i++){
      int next = IN[i];
      if(Getd(bill[now.second],bill[next]) <= 50 && Getd(bill[now.second],bill[next]) > 0)
	if(node[next] > now.first+Getd(bill[now.second],bill[next])){
	  node[next] = now.first+Getd(bill[now.second],bill[next]);
	  Q.push(P(node[next],next));
	  pre[next] = now.second;
	}
    }
  }

  vector<int> V;
  int prec = to;
  if(node[to] == INF) cout << "NA";
  else {
    V.push_back(to);
    while(pre[prec] != -1){
      V.push_back(pre[prec]);
      prec = pre[prec];
    }
  }
  reverse(V.begin(),V.end());
  for(int i = 0; i < V.size(); i++){
    if(i) cout << " ";
    cout << V[i];
  }
  cout << endl;
}

int main(){
  while(cin >> n && n){
    IN.clear();
    for(int i = 0; i < n; i++){
      int num;
      cin >> num;
      cin >> bill[num].x >> bill[num].y;
      IN.push_back(num);
    }
    cin >> m;
    for(int i = 0; i < m; i++){
      int f,t;
      cin >> f >> t;
      solve(f,t);
    }
  }
  return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>

using namespace std;

int n,m;
struct bill{
	int b,x,y;
	bill(int b,int x,int y):b(b),x(x),y(y){};
};
vector<bill> bi;
map<int,int> bn;
map<int,int> bnb;
typedef pair<double,int> P;
double d[10000];
int pr[10000];
double INF=10000000;

double sqr(int num){
	return sqrt((double)num);
}

int po2(int l){
	return l*l;
}

void dijk(int f,int t){
	fill(d,d+n+1,INF);
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0.0,f));
	d[f]=0.0;
	while(que.size()){
		P p=que.top();
		que.pop();
		double c=p.first;
		int v=p.second;
		if(d[v]<c)continue;
		for(int i=0;i<n;i++){
			double k=sqr(po2(abs(bi[v].x-bi[i].x))+po2(abs(bi[v].y-bi[i].y)));
			if(k<=50.0 && d[i]>c+k){
				d[i]=c+k;
				pr[i]=v;
				que.push(P(c+k,i));
			}
		}
	}
}

void rc(int f,int t){
	vector<int> prev;
	while(f!=t){
		prev.push_back(bnb[t]);
		t=pr[t];
	}
	prev.push_back(bnb[t]);
	sort(prev.begin(),prev.end());
	for(int i=0;i<prev.size();i++){
		if(i!=0)printf(" ");
		printf("%d",prev[i]);
	}
	printf("\n");
}

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		bi.clear();
		bn.clear();
		bnb.clear();
		for(int i=0;i<n;i++){
			int b,x,y;
			scanf("%d%d%d",&b,&x,&y);
			bi.push_back(bill(b,x,y));
			bn[b]=i;
			bnb[i]=b;
		}
		scanf("%d",&m);
		for(int i=0;i<m;i++){
			int f,t;
			scanf("%d%d",&f,&t);
			dijk(bn[f],bn[t]);
			if(d[bn[t]]!=INF)rc(bn[f],bn[t]);
			else printf("NA\n");
		}
	}
	return 0;
}

C++: #include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <cassert>

using namespace std;

const int MAX_V = 1001;
const int INF   = INT_MAX;

struct Edge {
  int to;
  int cost;
};

int          V;
vector<Edge> G[MAX_V];
int          d[MAX_V];
int          prev[MAX_V];

void dijkstra(int s) {
  typedef pair<int, int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d, d + V, INF);
  fill(prev, prev + V, -1);
  d[s] = 0;
  que.push(P(0, s));
  while (!que.empty()) {
    P   p = que.top(); que.pop();
    int v = p.second;
    if (d[v] < p.first)
      continue;
    for (int i = 0; i < (int)G[v].size(); i++) {
      Edge e = G[v][i];

      if (d[e.to] > d[v] + e.cost) {
        d[e.to]    = d[v] + e.cost;
        prev[e.to] = v;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

vector<int> get_path(int t) {
  vector<int> path;

  for (; t != -1; t = prev[t]) {
    path.push_back(t);
  }
  reverse(path.begin(), path.end());
  return path;
}


struct Building {
  int x;
  int y;
};

int distance2(Building *b1, Building *b2) {
  int dx = b1->x - b2->x;
  int dy = b1->y - b2->y;
  return dx * dx + dy * dy;
}

int name[MAX_V];
int rname[MAX_V];
Building building[MAX_V];

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0)
      break;
    V = n;

    for (int i = 0; i < n; i++) {
      G[i].clear();
    }
    for (int i = 0; i < n; i++) {
      int b;
      cin >> b;
      name[i] = b;
      rname[b] = i;
      cin >> building[i].x >> building[i].y;
    }
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        Building *b1 = building + i;
        Building *b2 = building + j;
        int       d2 = distance2(b1, b2);

        if (d2 <= 50 * 50) {
          int d1 = sqrt(d2);
          Edge e1 = {j, d1};
          G[i].push_back(e1);
          Edge e2 = {i, d1};
          G[j].push_back(e2);
        }
      }
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
      int s;
      int g;
      cin >> s >> g;
      dijkstra(rname[s]);
      if (d[rname[g]] == INF) {
        cout << "NA" << endl;
      } else {
        vector<int> path = get_path(rname[g]);
        for (int j = 0; j < (int)path.size(); j++) {
          cout << name[path[j]];
          if (j < (int)path.size() - 1)
            cout << " ";
        }
        cout << endl;
      }
    }
  }
  return 0;
}