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<cstring>
#include<set>

const int INF=-1;
unsigned int adjacive[1000][1000];
int field[1000][1000];
int prev[1000];
std::set<int> building;

int input();
void dijkstra(int start);
void output(int start,int goal);

int main()
{
	while(1)
	{
		int n;
		n=input();
		if(n==0)break;
		
		int m;
		std::cin>>m;
		for(int i=0;i<m;i++)
		{
			int bs,bg;
			std::cin>>bs>>bg;
			dijkstra(bs);
			output(bs,bg);
		}
	}
	return 0;
}

int input()
{
	int n;
	std::cin>>n;
	if(n==0)return 0;
	memset(field,0,sizeof(field));
	memset(adjacive,-1,sizeof(field));
	building.clear();

	for(int i=0;i<n;i++)
	{
		int b,x,y;
		std::cin>>b>>x>>y;
		field[y][x]=b;
		building.insert(b);
	}
	for(int y=0;y<1000;y++)
	{
		for(int x=0;x<1000;x++)
		{
			if(field[y][x]!=0)
			{
				for(int i=-50;i<=50;i++)
				{
					for(int j=-50;j<=50;j++)
					{
						if(i+y>=0&&i+y<1000&&j+x>=0&&j+x<1000&&field[i+y][j+x]&&i*i+j*j<=2500)//genarate adjacive matrix
						{
							adjacive[field[y][x]-1][field[y+i][x+j]-1]=i*i+j*j;
						}
					}
				}
			}
		}
	}
	
	return n;
}

void dijkstra(int start)
{
	bool visited[1000];
	unsigned int cost[1000];
	memset(visited,0,sizeof(visited));
	memset(cost,-1,sizeof(cost));
	memset(prev,-1,sizeof(prev));
	
	cost[start-1]=0;
	while(1)
	{
		int u=-1;
		for(int i=0;i<1000;i++)
		{
			if(building.count(i+1)==1&&!visited[i]&&(u==-1||cost[i]<cost[u]))
			{
				u=i;
			}
		}
		if(u==-1)break;
		visited[u]=true;
		for(int i=0;i<1000;i++)
		{
			if((long long)cost[i]-cost[u]>(long long)adjacive[u][i])
			{
				cost[i]=cost[u]+adjacive[u][i];
				prev[i]=u;
				
			}
		}
	}
	
	for(int i=0;i<=22;i++)
	{
		std::cout<<prev[i]<<std::endl;
	}
}

void output(int start,int goal)
{
	int temp[1000];
	int b=goal-1;
	int i=0;
	bool isNA=true;

	while(prev[b]!=-1)
	{
		temp[i]=b+1;
		i++;
		b=prev[b];
		isNA=false;
	}

	if(isNA)
	{
		std::cout<<"NA"<<std::endl;
	}
	else
	{
		std::cout<<start;
		for(i=i-1;i>=0;i--)
		{
			std::cout<<' '<<temp[i];
		}
		std::cout<<std::endl;
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

struct Bill
{
	int b, x, y;
};

#define SQR(x) ((x) * (x))
const int INF = 1 << 30;

int prv[1024];
bool dijkstra(vector<Bill>& bill, vint& ntoi, int s, int t)
{
	int V = bill.size();
	
	vint used(V, false);
	vint d(V, INF);
	d[s] = 0;
	
	while(true)
	{
		int v = -1;
		for(int u = 0; u < V; u++)
		{
			if(!used[u] && (v == -1 || d[u] < d[v]))
			{
				v = u;
			}
		}
		
		if(v == -1) break;
		
		used[v] = true;
		
		rep(u, V)
		{
			double drc = sqrt(SQR(bill[v].x - bill[u].x) + SQR(bill[v].y - bill[u].y));
			if(drc <= 50 && d[v] + drc < d[u])
			{
				d[u] = d[v] + drc;
				prv[u] = v;
			}
		}
	}
	
	return d[t] == INF;
}

int main()
{
    int n;
	
	while(cin >> n && n)
	{
		vector<Bill> bill(n);
		vint ntoi(1001, -1);
		rep(i, n)
		{
			cin >> bill[i].b >> bill[i].x >> bill[i].y;
			ntoi[bill[i].b] = i;
		}
		
		int m;
		cin >> m;
		rep(i, m)
		{
			int s, b;
			cin >> s >> b;
			
			memset(prv, -1, sizeof prv);
			
			if(dijkstra(bill, ntoi, ntoi[s], ntoi[b]))
			{
				cout << "NA" << endl;
			}
			else
			{
				vint path;
				for(int t = ntoi[b]; t != -1; t = prv[t]) path.push_back(bill[t].b);
				
				reverse(ALL(path));
				
				rep(i, path.size()) cout << path[i] << (i + 1 == path.size() ? "\n" : " ");
			}
		}
	}
}