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>
using namespace std;
int main(){
	int n;
	while(cin >> n , n){
		double g[n][n];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				g[i][j] = 100000000;
		int b[n] , x[n] , y[n];
		for(int i = 0; i < n; i++)
			cin >> b[i] >> x[i] >> y[i];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++){
				int xx = x[i] - x[j],
					   yy = y[i] - y[j];
				if(pow(xx , 2) + pow(yy , 2) <= 2500 && i != j)
					g[i][j] = g[j][i] = sqrt(pow(xx , 2) + pow(yy , 2));
			}
		int m;
		cin >> m;
		int s , go;
		for(int i = 0; i < m; i++){
			cin >> s >> go;
			s--; go--;
			vector <int> used(n,false);
			vector <int> gone(n,false);
			vector <double> dist(n,100000000);
			dist[s] = 0;
			gone[s] = 0;
			while(1){
				int va = -1;
				for(int j = 0; j < n; j++)
					if(used[j] == false && (va == -1 || dist[va] > dist[j]))
						va = j;
				if(va == -1)
					break;
				used[va] = true;
				for(int j = 0; j < n; j++){
					if(dist[j] >= dist[va] + g[va][j])
						gone[j] = va;
					dist[j] = min(dist[j] , dist[va] + g[va][j]);
				}
			}
			if(s == go)
				cout << s + 1 << " " << go + 1 << endl;
			else if(dist[go] == 100000000)
				cout << "NA" << endl;
			else{
				int kari = go;
				stack <int> out;
				while(1){
					out.push(gone[kari] + 1);
					kari = gone[kari];
					if(kari == s)
						break;
				}
				while(!out.empty()){
					cout << out.top() << " ";
					out.pop();
				}
				cout << go + 1 << endl;
			}
		}
	}
}

C++: #include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <cmath>
using namespace std;

struct Node {
    bool isDone;
    int x, y, cost, from, dist2Next;
};

const int INF = pow(2, 30);
const int MAX_N = 1000;
Node nodes[MAX_N + 1];
int n;

void dijkstra(int start, int end) {
    for (int i = 1; i <= n; i++) {
        nodes[i].isDone = false;
        nodes[i].cost = -1;
        nodes[i].from = -1;
        nodes[i].dist2Next = INF;
    }
    nodes[start].cost = 0;
    nodes[start].from = 0;
    while (true) {
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
            if (nodes[i].isDone == true || nodes[i].cost < 0) {
                continue;
            }
            qu.push(i);
        }
        if (qu.empty() == true) {
            break;
        }
        vector<int> dist2Next(n + 1, INF);
        while (qu.empty() == false) {
            int idx = qu.front();
            qu.pop();
            nodes[idx].isDone = true;
            int cost = nodes[idx].cost + 1;
            for (int i = 1; i <= n; i++) {
                int dist2 = pow(nodes[i].x - nodes[idx].x, 2) + pow(nodes[i].y - nodes[idx].y, 2);
                if (nodes[i].isDone == true || dist2 > pow(50, 2)) {
                    continue;
                }
                if (nodes[i].cost < 0 || cost < nodes[i].cost
                    || (cost == nodes[i].cost && dist2 < dist2Next[i])) {
                    nodes[i].cost = cost;
                    nodes[i].from = idx;
                    dist2Next[i] = dist2;
                }
            }
        }
    }
}

int main() {
    while (true) {
        cin >> n;
        if (n == 0) {
            break;
        }
        for (int i = 0; i < n; i++) {
            int b, x, y;
            cin >> b >> x >> y;
            nodes[b].x = x;
            nodes[b].y = y;
        }
        int m;
        cin >> m;
        for (int i = 0; i < m; i++) {
            int s, g;
            cin >> s >> g;
            dijkstra(s, g);
            string result;
            if (nodes[g].cost < 0) {
                result = "NA";
            } else {
                stringstream ss;
                ss << g;
                ss >> result;
                int from = nodes[g].from;
                while (from > 0) {
                    stringstream ss;
                    ss << from;
                    string temp;
                    ss >> temp;
                    result = temp + " " + result;
                    from = nodes[from].from;
                }
            }
            cout << result << endl;
        }
    }
}

C++: #include<iostream>
#include<cmath>
#define INF 9999999.9999999
using namespace std;

int n,m,a,b;
int id[1000];
double x[1000],y[1000];
double t[1000][1000];

void init();
void input();
void make_table();
void dijkstra(int,int);
int change(int);
int main(){
  while(cin>>n&&n){
    init();
    input();
    make_table();
    for(int i=0;i<m;i++){
      cin>>a>>b;
      
      dijkstra(change(a),change(b));
    }
  }
  return 0;
}

void init(){
  for(int i=0;i<1000;i++){
    for(int j=0;j<1000;j++){
      t[i][j]=INF;
    }
  }
}

void input(){
  for(int i=0;i<n;i++){
    cin>>id[i]>>x[i]>>y[i];
  }
  cin>>m;
}

void make_table(){
  double a;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j)continue;
      a=sqrt(pow(x[i]-x[j],2.0)+pow(y[i]-y[j],2.0));

      if(a<=50.0)t[i][j]=a;
    }
  }

  /*
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(t[i][j]==INF)cout<<"-- ";
      else{
	if((int)t[i][j]<10)cout<<' ';
	cout<<(int)t[i][j]<<' ';
      }
    }
    cout<<endl;
  }
  */
}

void dijkstra(int S,int T){
  //cout<<"S T "<<S<<' '<<T<<endl;
  int pi[1000];
  int mini_no;
  bool vd[1000];
  double u[1000];
  double mini;
  

  for(int i=0;i<n;i++){
    vd[i]=false;
    u[i]=INF;
  }

  u[S]=0.0;
  pi[S]=-1;

  while(1){
    mini=INF;
    for(int i=0;i<n;i++){
      if(mini>u[i]&&vd[i]==false){
	mini=u[i];
	mini_no=i;
      }
    }

    if(mini==INF)break;
    vd[mini_no]=true;

    for(int i=0;i<n;i++){
      if(t[mini_no][i]==INF)continue;
      if(u[i]>u[mini_no]+t[mini_no][i]){
	u[i]=u[mini_no]+t[mini_no][i];
	pi[i]=mini_no;
      }
    }
  }


  int ans[1000],cnt=0;
  
    
  if(u[T]==INF)cout<<"NA"<<endl;
  else {
    //cout<<vd[T]<<endl;
    for(;T!=-1;T=pi[T])ans[cnt++]=T;


    for(int i=cnt-1;i>=0;i--){
      if(i!=cnt-1)cout<<' ';
      cout<<id[ans[i]];
    }
    cout<<endl;
  }
}

int change(int x){
  for(int i=0;i<n;i++){
    if(id[i]==x)return i;
  }
}