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 <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1 << 28
#define EPS 1e-10

using namespace std;

struct Point 
{
    double x, y;
    Point(double x=0, double y=0) : x(x), y(y) {}
    
	double distance (const Point &o) const 
	{
        return sqrt((x - o.x) * (x - o.x) + (y - o.y) * (y - o.y));
    }

    Point operator+(const Point &o) const 
	{
        return Point(x+o.x, y+o.y);
    }
 
    Point operator-(const Point &o) const 
	{
        return Point(x-o.x, y-o.y);
    }
 	
    Point operator*(const double m) const 
	{
   	   return Point(x*m, y*m);
    }

    Point operator/(const double d) const 
	{
       return Point(x/d, y/d);
    }

    double cross(const Point &o) const 
	{
       return x * o.y - y * o.x;
    }
 
    double dot(const Point &o) const 
	{
        return x * o.x + y * o.y;
    }
 
    double atan() const 
	{
        return atan2(y, x);
    }

    double norm() const 
	{
        return sqrt(dot(*this));
    }

	double area_abs(const Point &a,const Point &b) const
	{
		double t = (a.x - x) * (b.y - y);
		double t2 = (a.y - y) * (b.x - x);
		double areas = abs(t-t2);
		return areas/2;
	}

	//符号付き面積
	double area(const Point &a,const Point &b)
	{
		return ((a.x - x) * (b.y - y)) + ((b.x - x) * (y - a.y));
	}
	//線分abが自身の含まれているのかどうか判断する
	int between(const Point &a,const Point &b)
	{
		if(area(a,b) != 0) return 0;

		if(a.x != b.x)
		{
			return ((a.x <= x) && (x <= b.x) || (a.x >= x) && (x >= b.x));
		}
		else
		{
			return ((a.y <= y) && (y <= b.y) || (a.y >= y) && (y >= b.y));
		}
	}

	double distance_seg(const Point& a,const Point& b)
	{
		if((b-a).dot(*this-a) < EPS) 
		{
			return (*this-a).norm();
		}
		if((a-b).dot(*this-b) < EPS)
		{
			return (*this-b).norm();
		}
		return abs((b-a).cross(*this-a)) / (b-a).norm();
	}

	//点a,b,cからなる三角形の中に自身が含まれているかどうか
	bool hitPolygon(const Point& a,const Point& b,const Point& c)
	{
		double t = (b-a).cross(*this-b);
		double t2 = (c-b).cross(*this-c);
		double t3 = (a-c).cross(*this-a);
		
		if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0))
		{
			return 1;
		}

		return 0;
	}
};

double cost[1000][1000];
bool used[1000];
int d[1000];
int prev[1000];

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

		rep(u,n)
		{
			if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}

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

		rep(u,n)
		{
			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;
}

int main()
{
	int n;
	while(cin >> n && n)
	{
		vector<Point> p;
		vector<int> number;
		rep(i,1000) rep(j,1000) cost[i][j] = INF;

		rep(i,n)
		{
			int num,a,b;
			cin >> num >> a >> b;

			p.push_back(Point(a,b));
			number.push_back(num);
		}

		rep(i,n)
		{
			REP(j,i+1,n)
			{
				if(p[i].distance(p[j]) <= 50.0)
				{
					cost[i][j] = p[i].distance(p[j]);
					cost[j][i] = p[i].distance(p[j]);
				}
			}
		}

		int m;
		cin >> m;

		rep(i,m)
		{
			int from,to;
			cin >> from >> to;

			from--;
			to--;

			dijkstra(from,n);

			if(d[to] == INF)
			{
				cout << "NA" << endl;
			}
			else
			{
				vector<int> ans = get_path(to);
				bool flag = true;
				rep(k,ans.size())
				{
					if(flag) flag = false;
					else cout << " ";

					cout << ans[k] + 1;
				}
				cout << endl;
			}
		}
	}
	return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;

const double EPS = 1e-6;

struct Building{
	int x, y;
};

struct Edge{
	int to;
	double cost;
	Edge(){}
	Edge(const int &_to, const double &_cost){
		to = _to; cost = _cost;
	}
};

struct Data{
	int n;
	double cost;
	Data(){}
	Data(const int &_n, const double &_cost){
		n = _n; cost = _cost;
	}
	bool operator < (const Data &a) const{
		return cost > a.cost;
	}
};

double GetDistance(const Building &b1, const Building &b2){
	double dx = b1.x - b2.x, dy = b1.y - b2.y;
	return sqrt(dx*dx + dy*dy);
}

vector<Edge> e[1000];

int main(){
	int N, M, B, S, G;

	while(cin >> N, N){
		Building v[1000];
		for(int i = 0; i < N; i++) e[i].clear();

		for(int i = 0; i < N; i++){
			cin >> B; B--;
			cin >> v[B].x >> v[B].y;
		}

		for(int i = 0; i < N; i++){
			for(int j = i+1; j < N; j++){
				double dist = GetDistance(v[i], v[j]);
				if(dist <= 50){
					e[i].push_back( Edge(j, dist) );
					e[j].push_back( Edge(i, dist) );
				}
			}
		}

		cin >> M;
		for(int j = 0; j < M; j++){
			cin >> S >> G; S--; G--;

			priority_queue<Data> pq;
			Data pq_top;
			pq.push( Data(S, 0) );
			double memo[1000];
			fill_n(memo, N, -1);
			bool na = true;

			while( !pq.empty() ){
				pq_top = pq.top(); pq.pop();
			
				if(memo[pq_top.n] > -0.5) continue;
				memo[pq_top.n] = pq_top.cost;
				if(pq_top.n == G){
					na = false; break;
				}

				for(int i = 0; i < e[pq_top.n].size(); i++){
					pq.push( Data( e[pq_top.n][i].to, pq_top.cost + e[pq_top.n][i].cost ) );
				}
			}

			if(na){
				puts("NA"); break;
			}

			stack<int> ans;
			while(true){
				ans.push(G);
				if(G == S) break;
				for(int i = 0; i < e[G].size(); i++){
					if( abs(memo[G] - memo[ e[G][i].to ] - e[G][i].cost) < EPS){
						G = e[G][i].to; break;
					}
				}
			}
		
			printf("%d", ans.top()+1 ); ans.pop();
			while( !ans.empty() ){
				printf(" %d", ans.top()+1 ); ans.pop();
			}puts("");
		}
	}
	return 0;
}