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<vector>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1e9
using namespace std;
struct S{
	vector<int> his;
	int p; double d;
	bool operator<(const S &a)const{
		return d<a.d;
	}
};
int main(){
	int n,m,s,g;
	while(cin>>n,n){
		double d[n][n],x[n],y[n],cost[n]; int id[n],b[1001];
		rep(i,n)cin>>id[i]>>x[i]>>y[i],b[id[i]]=i;
		rep(i,n)rep(j,n)d[i][j]=hypot(x[i]-x[j],y[i]-y[j]);
		for(cin>>m;m--;){
			cin>>s>>g;
			S cs,ns; cs.p=b[s]; cs.his.push_back(s);
			priority_queue<S> F; F.push(cs); vector<int> ans;
			rep(i,n)cost[i]=INF; cost[cs.p]=0;
			while(!F.empty()){
				cs=F.top(); F.pop();
				rep(i,n)if(0<d[cs.p][i]&&d[cs.p][i]<=50)if(cost[i]>(ns.d=cost[cs.p]+d[cs.p][i])){
					cost[i]=ns.d, ns.p=i, ns.his=cs.his, ns.his.push_back(id[i]);
					F.push(ns);
					if(i==b[g])ans=ns.his;
				}
			}
			if(cost[b[g]]==INF)cout<<"NA"<<endl;
			else rep(i,ans.size())cout<<ans[i]<<(i==ans.size()-1?"\n":" ");
		}
	}
	return 0;
}

C++: #include<bits/stdc++.h>
#define F first
#define S second
#define INF (1<<30)
using namespace std;
typedef pair<double,double> dP;
typedef pair<int,double> To;
typedef pair<double,int> Que;
typedef pair<int,int> P;
typedef pair< P , P > PP;
typedef struct{
  vector<To> to;
  dP zahyo;
  double mincost;
  int minpos;
  int num;
}Edge;
main(){
  Edge bill[1005];
  int n,m,s,g;
  while(1){
    cin>>n;
    for(int i=0;i<n;i++){
      int b;
      double x,y;
      cin>>b>>x>>y;
      bill[b].num=b;
      bill[b].zahyo.F=x;
      bill[b].zahyo.S=y;
    }
    for(int i=2;i<=n;i++){
      for(int j=1;j<i;j++){
	double ix=bill[i].zahyo.F;
	double iy=bill[i].zahyo.S;
	double jx=bill[j].zahyo.F;
	double jy=bill[j].zahyo.S;
	double kyori=sqrt(pow(fabs(ix-jx),2)+pow(fabs(iy-jy),2));
	if(kyori<=50){
	  bill[i].to.push_back(To(j,kyori));
	  bill[j].to.push_back(To(i,kyori));
	}
      }
    }
    cin>>m;
    for(int i=0;i<m;i++){
      for(int i=1;i<=n;i++){
	bill[i].mincost=INF;
	bill[i].minpos=-1;
      }
      cin>>s>>g;
      priority_queue<Que,vector<Que>,greater<Que> > que;
      que.push(Que(0,s));
      bill[s].mincost=0;
      bill[s].minpos=s;
      while(!que.empty()){
	Que now=que.top();
	//cout<<now.F<<" "<<now.S<<endl;
	int nb=now.S;
	que.pop();
	int size=bill[nb].to.size();
	if(bill[nb].mincost<now.F) continue;
	//cout<<"size="<<size<<endl;
	for(int i=0;i<size;i++){
	  To tob=bill[nb].to[i];
	  if(bill[tob.F].mincost>bill[nb].mincost+tob.S){
	    bill[tob.F].mincost=bill[nb].mincost+tob.S;
	    bill[tob.F].minpos=nb;
	    que.push(Que(bill[tob.F].mincost,tob.F));
	  }
	}
      }
      if(bill[g].minpos==-1){
	cout<<"NA"<<endl;
      }
      else{
	stack<int> st;
	int p=g;
	while(p!=s){
	  st.push(p);
	  p=bill[p].minpos;
	}
	st.push(s);
	while(st.size()>1){
	  cout<<st.top()<<" ";
	  st.pop();
	}
	cout<<st.top()<<endl;
	st.pop();
      }
    }
  }
}

C++: #include<vector>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const double EPS = 1e-8;
int main(){
	int n,m,s,g,t;
	while(cin>>n,n){
		double adj[n][n]; rep(i,n)rep(j,n)adj[i][j]=60;
		int x[n],y[n];
		rep(i,n)cin>>t>>x[i]>>y[i];
		rep(i,n)rep(j,i)adj[i][j]=adj[j][i]=hypot(x[i]-x[j],y[i]-y[j]);
		
		cin>>m;
		while(m--){
			cin>>s>>g,s--,g--;
			double cost[n]; rep(i,n)cost[i]=99999999; cost[s]=0;
			vector<vector<int> > path(n); path[s].push_back(s);
			
			vector<int> frontier,next; frontier.reserve(n),next.reserve(n);
			frontier.push_back(s);
			for(;cost[g]==99999999&&!frontier.empty();){
				next.clear();
				rep(i,frontier.size()){
					rep(j,n){
						t=frontier[i];
						if(adj[t][j]<50+EPS&&cost[j]+EPS>cost[t]+adj[t][j]){
							cost[j]=cost[t]+adj[t][j];
							path[j]=path[t],path[j].push_back(j);
							next.push_back(j);
						}
					}
				}
				frontier=next;
			}
			if(cost[g]==99999999)cout<<"NA"<<endl;
			else rep(i,path[g].size())
			cout<<path[g][i]+1<<(i==path[g].size()-1?"\n":" ");
		}
	}
	return 0;
}

C++: #include<iostream>
#include<iomanip>
using namespace std;
#include<vector>
#include<queue>
#include<limits>
template<typename T>
vector<int>dijkstra(int s,const vector<vector<pair<int,T> > >&G,T INF=numeric_limits<T>::max())
{
	int n=G.size();
	vector<T>d(n,INF);
	vector<int>parent(n,-1);
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >P;
	d[s]=0;
	P.push(make_pair(d[s],s));
	while(!P.empty())
	{
		pair<T,int>p=P.top();P.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		for(const pair<int,T>&e:G[v])
		{
			int u=e.first;
			T cost=d[v]+e.second;
			if(d[u]>cost)
			{
				d[u]=cost;
				parent[u]=v;
				P.push(make_pair(d[u],u));
			}
		}
	}
	return parent;
}
#include<cmath>
#include<algorithm>
int x[100],y[100];
main()
{
	int N;
	while(cin>>N,N)
	{
		vector<vector<pair<int,double> > >G(N);
		for(int i=0;i<N;i++)
		{
			int b;cin>>b;b--;
			cin>>x[b]>>y[b];
		}
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)
		{
			if(i==j)continue;
			double dis=hypot(x[i]-x[j],y[i]-y[j]);
			if(dis<=50)G[i].push_back(make_pair(j,dis));
		}
		int m;cin>>m;
		for(;m--;)
		{
			int s,g;cin>>s>>g;
			s--,g--;
			vector<int>p=dijkstra(s,G);
			if(p[g]==-1)cout<<"NA"<<endl;
			else
			{
				vector<int>ok;
				ok.push_back(g);
				while(ok.back()!=s)
				{
					ok.push_back(p[ok.back()]);
				}
				reverse(ok.begin(),ok.end());
				for(int i=0;i<ok.size();i++)
				{
					cout<<ok[i]+1<<(i+1==ok.size()?"\n":" ");
				}
			}
		}
	}
}