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>
#define INF 1000000000000LL
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n;
double G[101][101];

void dijkstra(int s,int g){
  ll D[101],from[101];
  for(int i=0;i<101;i++) D[i]=INF;
  
  priority_queue<P,vector<P>,greater<P> > Q;
  D[s]=0;
  Q.push(P(0,s));
  while(!Q.empty()){
    P t=Q.top(); Q.pop();
    ll pos=t.second,cost=t.first;
    if(pos==g) break;
    if(D[pos]<cost) continue;
    
    for(int i=0;i<n;i++){
      if(G[pos][i]==-1||i==pos)continue;
      if(cost+1<D[i]){
	Q.push(P(cost+1,i));
	D[i]=cost+1;
	from[i]=pos;
      }
    }
  }

  if(D[g]==INF){cout<<"NA"<<endl;return;}
    
  vector<int> res;
  res.push_back(g);
  int pos=g;
  while(pos!=s){
    pos=from[pos];
    res.push_back(pos);
  }

  for(int i=0;i<res.size();i++){
    if(i) cout<<" ";
    cout<<res[res.size()-1-i]+1;
  }
  cout<<endl;
}


int main(){
  while(cin>>n,n){

  double x[101],y[101];
  for(int i=0;i<n;i++){
    int b;
    cin>>b;
    cin>>x[b-1]>>y[b-1];
  }
  
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++){
      ll X=(x[i]-x[j]);
      ll Y=(y[i]-y[j]);
      ll dis=X*X+Y*Y;
      if(dis>50*50)G[i][j]=G[j][i]=-1;
      else G[i][j]=G[j][i]=dis;
    }

  int m;
  cin>>m;
  while(m--){
    int s,g;
    cin>>s>>g;
    dijkstra(s-1,g-1);
  }
  }
  return 0;
}

C++: #include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back


int main() {
    int n;
    while(cin>>n){
        if(n==0)break;
        
        int b[1000]={},x[1000]={},y[1000]={};
        rep(i,n){
            cin>>b[i]>>x[i]>>y[i];
            b[i]--;
        }
        
        int data[1000][1000]={};
        rep(i,n) rep(j,n) data[i][j]=99999999;
        int prev[1000][1000]={};

        rep(i,n){
            rep(j,n){
                ll res=pow(x[i]-x[j],2) + pow(y[i]-y[j],2);
                if(res<=2500){
                    data[i][j]=sqrt(res);
                    prev[i][j]=i;
                }
            }
        }
        
        rep(k,n){
            rep(i,n){
                rep(j,n){
                    if( data[i][k]+data[k][j] < data[i][j] ){
                        data[i][j] = data[i][k]+data[k][j];
                        prev[i][j]=prev[k][j];
                    }
                    data[i][j]=min( data[i][k]+data[k][j] , data[i][j] );
                }
            }
        }
        
        int m;
        cin>>m;
        
        int s,g;
        rep(i,m){
            cin>>s>>g;
            s--,g--;
            if(data[s][g]!=99999999){
                stack<int> ans;
                int pre=g;
                while(pre!=s){
                    ans.push(pre);
                    pre=prev[s][pre];
                }
                cout<<s+1;
                while(ans.size()){
                    cout<<" "<<ans.top()+1;
                    ans.pop();
                }
                cout<<endl;
            }
            else cout<<"NA"<<endl;
        }
    }
    return 0;
}

C++: #include<math.h>
using namespace std;
#define MAX 100
#define INFTY (1 << 21)

struct Building{ int x, y; };

int n;
Building B[MAX+1];
double D[MAX+1];
int P[MAX+1];

double getDistance( Building b1, Building b2 ){
    return sqrt(1.0*(b1.x-b2.x)*(b1.x-b2.x) + (b1.y - b2.y)*(b1.y - b2.y));
}

void dijkstra( int s ){
    bool visited[MAX+1];
    for ( int i = 1; i <= n; i++ ){
	D[i] = INFTY;
	P[i] = -1;
	visited[i] = false;
    }

    D[s] = 0.0;

    while(1){
	double minv = INFTY;
	int u = 0;
	for ( int i = 1; i <= n; i++ ){
	    if ( visited[i] ) continue;
	    if ( minv > D[i] ){
		minv = D[i];
		u = i;
	    }
	}
	if ( minv == INFTY ) break;
	visited[u] = true;

	for ( int v = 1; v <= n; v++ ){
	    if ( visited[v] ) continue;
	    double d = getDistance( B[u], B[v] );
	    if ( d <= 50.0 && D[u] + d < D[v] ){
		D[v] = D[u] + d;
		P[v] = u;
	    }
	}
    }
}

void print( int i, bool f){
    if ( i == -1 ) return;
    print(P[i], true);
    cout << i;
    if ( f ) cout << " ";
}

void printPath( int s, int g ){
    if ( D[g] == INFTY ) {
	cout << "NA" << endl;
	return;
    }
    print(g, false);
    cout << endl; 
}

main(){
    while( cin >> n && n ){
	int x;
	for ( int i = 1; i <= n; i++ ){
	    cin >> x;
	    cin >> B[x].x >> B[x].y;
	}
	int query; cin >> query;
	int s, g;
	for ( int i = 0; i < query; i++ ){
	    cin >> s >> g;
	    dijkstra(s);
	    printPath(s, g);
	}
    }
}