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 <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>


typedef long long ll;
const double Eps = 1e-4;

using namespace std;

typedef pair<int, double> P;
double dis(int x, int y)
{
	return sqrt((double)x*x+y*y);
}
int main()
{
	int n;
	while (scanf("%d", &n), n)
	{
		int no[1000];
		int x[1001], y[1001];
		for (int i = 0; i < n; ++i)
		{
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			no[i] = a;
			x[a] = b;
			y[a] = c;
		}
		vector<P> reach[1001];
		for (int i = 0; i < n; ++i)
		{
			for (int j = i+1; j < n; ++j)
			{
				double t = dis(x[no[i]]-x[no[j]], y[no[i]]-y[no[j]]);
				if (t < 50 + Eps)
				{
					reach[no[i]].push_back(P(no[j], t));
					reach[no[j]].push_back(P(no[i], t));
				}
			}
		}
		
		int m;
		scanf("%d", &m);
		while (m--)
		{
			int from[1001];
			double d[1001];
			const int Inf = 100000000;
			for (int i = 0; i < 1001; ++i)
				d[i] = from[i] = Inf;
			int s, g;
			scanf("%d %d", &s, &g);
			priority_queue<P, vector<P>, greater<P> > nodes;
			nodes.push(P(0, s));
			d[s] = 0;
			from[s] = -1;
			while (!nodes.empty())
			{
				P v = nodes.top();
				nodes.pop();
				int id = v.second;
				if (id == g)
					break;
				else if (v.first > d[id])
					continue;

				for (int i = 0; i < reach[id].size(); ++i)
				{
					int to = reach[id][i].first;
					double cost = reach[id][i].second;
					if (v.first + cost < d[to])
					{
						d[to] = v.first + cost;
						from[to] = id;
						nodes.push(P(d[to], to));
					}
				}
			}
			if (d[g] != Inf)
			{
				vector<int> path;
				for (int i = g; i != -1; i = from[i])
					path.push_back(i);
				for (int i = path.size() - 1; i > 0; --i)
					printf("%d ", path[i]);
				printf("%d\n", path[0]);
			}
			else
				puts("NA");
		}
	}

	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]);
	reverse(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<iostream>
#include<cmath>
#include<vector>
#define MAX 1000+1
#define INF 999999
using namespace std;

double data[MAX][MAX];
int path[MAX];
double dist[MAX];

typedef struct node{
	double x,y;
} build;

void parse(int i, vector<int> &ans){
	if(i==-1) return;
	else{
		parse(path[i], ans);
		ans.push_back(i);
	}
}


void hantei(int s, int g, int n){
	bool visited[MAX];
	
	for(int i=0; i<n; i++){
		visited[i] = false;
		dist[i] = INF;
	}
	
	dist[s] = 0.0;
	path[s] = -1;
	
	while(1){
		int next;
		int min = INF;
		
		for(int i=0; i<n; i++){
			if( visited[i] ) continue;
			if( dist[i] < min){
				min = dist[i];
				next = i;
			}
		}
		
		if(min == INF) break;
		
		visited[next] = true;
		
		for(int j=0; j<n; j++){
			if( visited[j] ) continue;
			if( dist[next] + data[next][j] < dist[j]){
				dist[j] = dist[next] + data[next][j];
				path[j] = next;
			}
		}
	}
	
	if(dist[g] == INF) cout << "NA" << endl;
	else{
		vector<int> ans;
		parse(g,ans);
		for(int i=0; i<ans.size(); i++){
			if( i ) cout << " ";
			cout << ans[i]+1;
		}
	cout << endl;
	}
}	
	
int main(){
	build b[MAX];
	int n,m,num,s,g;
	while(cin >> n){
		if(n==0) break;
		for(int i=0; i<n; i++){
			cin >> num;
			num--;
			cin >> b[num].x >> b[num].y;
		}
		
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(i==j){
					data[i][j] = 0;
					continue;
				}
				data[i][j] = sqrt(pow(b[i].x - b[j].x, 2) + pow(b[i].y - b[j].y, 2));
				if(data[i][j] > 50) data[i][j] = INF;
				
			}
		}
		
		cin >> m;
		for(int i=0; i<m; i++){
			cin >> s >> g;
			hantei(s-1,g-1,n);
		}
	}
	return 0;
}