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 <complex>

using namespace std;

const double INF = 1000000;

int main()
{
    for (;;) {
        int n, m;
        complex<double> bb[1000];
        double di[1000][1000];
        int sg[1000][2];

        // read bill
        scanf("%d", &n);
        if (n == 0)
            break;
        for (int i = 0; i < n; ++i) {
            int b, x, y;
            scanf("%d %d %d", &b, &x, &y);
            bb[b - 1] = complex<double>(x, y);
        }

        // eval distance
        // TODO: ビルの番号が 0 から n - 1 と仮定
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                di[i][j] = di[j][i] = abs(bb[i] - bb[j]);
                if (di[i][j] > 50)
                    di[i][j] = di[j][i] = INF;
                //printf("  %d to %d is %f\n", i, j, di[i][j]);
            }
        }

        // read move
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &sg[i][0], &sg[i][1]);
            --sg[i][0];
            --sg[i][1];
        }

        for (int ci = 0; ci < m; ++ci) {
            double dt[1000];
            bool vi[1000] = {};
            int from[1000] = {};
            for (int i = 0; i < n; ++i)
                dt[i] = INF;

            // Dijkstra
            int p = sg[ci][0];
            dt[p] = 0;
            from[p] = -1;
            for (;;) {
                vi[p] = true;
                //printf("  - search %d\n", p+1);
                for (int j = 0; j < n; ++j) {
                    if (!vi[j] && di[p][j] != INF && dt[j] > dt[p] + di[p][j]) {
                        dt[j] = dt[p] + di[p][j];
                        from[j] = p;
                    }
                }

                int min = INF;
                for (int j = 0; j < n; ++j) {
                    if (!vi[j] && dt[j] < min) {
                        p = j;
                        min = dt[j];
                    }
                }
                if (min == INF)
                    break;
            }

            if (dt[sg[ci][1]] == INF) {
                printf("NA\n");
            } else {
                int i, p, list[1000];
                p = list[0] = sg[ci][1];
                for (i = 1; p != -1; ++i) {
                    p = list[i] = from[p];
                }
                for (i -= 2; i >= 0; --i)
                    printf("%d%c", list[i] + 1, i == 0 ? '\n' : ' ');
            }
        }

    }

    return 0;
}

C++: #include<iostream>
#include<vector>
#include<complex>
#define rep(i,n) for(int i = 0;i < n ; ++i)

using namespace std;

using ll = long long;
using Point = complex<double>;


void solve(int n){
    Point p[n];
    rep(i,n){
        int a,b,c;
        cin>>a>>b>>c;
        --a;
        p[a] = Point(b,c);
    }
    double dist[n][n];
    double d[n][n];
    rep(i,n)dist[i][i]=0;
    rep(i,n)rep(j,n){
        if(i==j)continue;
        if(abs(p[i]-p[j])<=50)dist[i][j]=abs(p[i]-p[j]);
        else dist[i][j]=1e9;
    }
    rep(i,n)rep(j,n){
        d[i][j]=dist[i][j];
    }
    rep(i,n)rep(j,n)rep(k,n){
        dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
    }
    int m;
    cin>>m;
    while(m--){
        int s,t;
        cin>>s>>t;
        --s;--t;
        if(dist[s][t]>=1e8){
            cout<<"NA"<<endl;
            continue;
        }
        while(s!=t){
            cout<<s+1<<" ";
            rep(i,n){
                if(s!=i&&abs(d[s][i]+dist[i][t]-dist[s][t])<1e-5){
                    s=i;
                    break;
                }
            }
        }
        cout<<t+1<<endl;
    }
}

int main(){
    int n;
    while(cin>>n,n!=0)solve(n);
}

C++: #include <bits/stdc++.h>

using namespace std;

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define Get(t, i) get<(i)>((t))
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto& a : b)
#define int long long

const int inf = 1 << 25;
const ll INF = 1LL << 55;

struct edge
{
  int to; double cost;
  edge(){}
  edge(int to, double cost):to(to), cost(cost){}
};

int n;
vector< vector<edge> > graph;

void dijkstra(int s, int g)
{
  typedef pair<double, int> Pd;
  
  priority_queue<Pd, vector<Pd>, greater<Pd> > que;  
  vector<double> mincost(n, inf);
  vector<int> prevv(n, -1);
  
  que.push(Pd(0.0, s));
  mincost[s] = 0.0;
  
  while(!que.empty()) {
    Pd p = que.top(); que.pop();
    if(p.S == g) break;
    if(mincost[p.S] < p.F) continue;
    for(edge e : graph[p.S]) {
      if(e.cost + p.F < mincost[e.to]) {
	mincost[e.to] = e.cost + p.F;
	prevv[e.to] = p.S;
	que.push(Pd(mincost[e.to], e.to));
      }
    }
  }
  if(mincost[g] == INF) {
    puts("NA");
    return;
  }
  vector<int> ans;
  for(int v = g; v != -1; v = prevv[v]) {
    ans.push_back(v+1);
  }
  reverse(all(ans));
  for(int i = 0; i < ans.size(); i++) {
    if(i) cout << " ";
    cout << ans[i];
  }
  cout << endl;
}

double dist(Pi a, Pi b)
{
  return sqrt((a.F-b.F)*(a.F-b.F) + (a.S-b.S)*(a.S-b.S));
}

signed main()
{
  while(cin >> n, n) {
    vector<Pi> pos(n);
    graph.clear(); graph.resize(n);
    for(int i = 0; i < n; i++) {
      int b; cin >> b; b--;
      cin >> pos[b].F >> pos[b].S;
    }
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	double d;
	if((d = dist(pos[i], pos[j])) <= 50.0){
	  graph[i].push_back(edge(j, d));
	}
      }
    }
    int m; cin >> m;
    while(m--) {
      int s, g; cin >> s >> g;
      s--, g--;
      dijkstra(s, g);
    }
  }
  return 0;
}