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 <bits/stdc++.h>

using namespace std;

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define Get(t, i) get<(i)>((t))
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto& a : b)
#define int long long

const int inf = 1 << 25;
const ll INF = 1LL << 55;

struct edge
{
  int to; double cost;
  edge(){}
  edge(int to, double cost):to(to), cost(cost){}
};

int n;
vector< vector<edge> > graph;

void dijkstra(int s, int g)
{
  typedef pair<double, int> Pd;
  
  priority_queue<Pd, vector<Pd>, greater<Pd> > que;  
  vector<double> mincost(n, INF);
  vector<int> prevv(n, -1);
  
  que.push(Pd(0.0, s));
  mincost[s] = 0.0;
  
  while(!que.empty()) {
    Pd p = que.top(); que.pop();
    if(p.S == g) break;
    if(mincost[p.S] < p.F) continue;
    for(edge e : graph[p.S]) {
      if(e.cost + p.F < mincost[e.to]) {
	mincost[e.to] = e.cost + p.F;
	prevv[e.to] = p.S;
	que.push(Pd(mincost[e.to], e.to));
      }
    }
  }
  if(mincost[g] == INF) {
    puts("NA");
    return;
  }
  vector<int> ans;
  for(int v = g; v != -1; v = prevv[v]) {
    ans.push_back(v+1);
  }
  reverse(all(ans));
  for(int i = 0; i < ans.size(); i++) {
    if(i) cout << " ";
    cout << ans[i];
  }
  cout << endl;
}

double dist(Pi a, Pi b)
{
  return sqrt((a.F-b.F)*(a.F-b.F) + (a.S-b.S)*(a.S-b.S));
}

signed main()
{
  while(cin >> n, n) {
    vector<Pi> pos(n);
    graph.clear(); graph.resize(n);
    for(int i = 0; i < n; i++) {
      int b; cin >> b; b--;
      cin >> pos[b].F >> pos[b].S;
    }
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	double d;
	if((d = dist(pos[i], pos[j])) <= 50.0){
	  graph[i].push_back(edge(j, d));
	}
      }
    }
    int m; cin >> m;
    while(m--) {
      int s, g; cin >> s >> g;
      s--, g--;
      dijkstra(s, g);
    }
  }
  return 0;
}

C++: #include<iostream>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<algorithm>
#define INF 1000000000

using namespace std;

void dijkstra(int);
vector<int>get_path(int);

int V,prev[1001];
double cost[1001][1001],d[1001];
bool used[1001];

int main(void){

  int b[1001],m,s,g;
  double x[1001],y[1001];
  while(cin >> V,V){
    for(int i=0;i<V;i++){
      cin >> b[i] >> x[i] >> y[i];
    }

    for(int i=0;i<=V;i++)
      for(int j=0;j<=V;j++)
	cost[i][j]=INF;

    for(int i=0;i<V;i++){
      for(int j=0;j<V;j++){
	if(i!=j){
	  double a=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
	  if(50.>=a)cost[b[i]][b[j]]=cost[b[j]][b[i]]=a;
	}
      }
    }
    
    cin >> m;
    for(int i=0;i<m;i++){
      cin>> s >> g;
      
	dijkstra(s);
	if(used[g]){
	  vector<int>p=get_path(g);
	  for(int j=0;j<p.size();j++){
	    cout << p[j];
	    if(j!=p.size()-1)cout <<" ";
	    else cout << endl;
	    
	  }
	}
	else cout << "NA" << endl; 
    }
  }
  
  return 0;
}

void dijkstra(int s){
  fill(d,d+V+1,INF);
  fill(used,used+V+1,false);
  fill(prev,prev+V+1,-1);
  d[s]=0;

  while(true){
    int v=-1;
    for(int u=1;u<=V;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }

    if(v==-1 || d[v]==INF)break;
    used[v]=true;

    for(int u=1;u<=V;u++){
      if(d[u]>d[v]+cost[v][u]){
	d[u]=d[v]+cost[v][u];
	prev[u]=v;
      }
    }
  }
}

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;
}