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++: // 2011/08/25 Tazoe



#include <iostream>

#include <climits>
#include <stack>
#include <cmath>

using namespace std;



int main()

{

	while(true){

		int n;

		cin >> n;

		if(n==0)

			break;



		int B[1000][3];

		for(int i=0; i<n; i++)

			cin >> B[i][0] >> B[i][1] >> B[i][2];

/*

		for(int i=0; i<n; i++)

			cout << B[i][0] << ' ' << B[i][1] << ' ' << B[i][2] << endl;

*/

		double D[1000][1000];

		for(int i=0; i<n; i++){

			for(int j=0; j<n; j++){

				double dis = sqrt((B[i][1]-B[j][1])*(B[i][1]-B[j][1])+(B[i][2]-B[j][2])*(B[i][2]-B[j][2]));

				if(dis<=50.0)

					D[i][j] = dis;

				else

					D[i][j] = 100000.0;

			}

		}


		int P[1000][1000];

		for(int i=0; i<n; i++)

			for(int j=0; j<n; j++)

				P[i][j] = i;

/*
		for(int i=0; i<n; i++){

			for(int j=0; j<n; j++){

				if(D[i][j]==INT_MAX)

					cout << '-' << ' ';

				else

					cout << P[i][j] << ' ';

			}

			cout << endl;

		}

*/
		for(int k=0; k<n; k++){
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					if(D[i][j]>D[i][k]+D[k][j]){
						D[i][j] = D[i][k]+D[k][j];
						P[i][j] = P[k][j];
					}
				}
			}
		}
/*
		for(int i=0; i<n; i++){

			for(int j=0; j<n; j++){

				if(D[i][j]==INT_MAX)

					cout << '-' << ' ';

				else

					cout << P[i][j] << ' ';

			}

			cout << endl;

		}

*/
		int m;
		cin >> m;

		for(int i=0; i<m; i++){
			int s, g;
			cin >> s >> g;
			int S, G;
			for(int j=0; j<n; j++){
				if(B[j][0]==s)
					S = j;
				if(B[j][0]==g)
					G = j;
			}

			if(D[S][G]==100000.0){
				cout << "NA" << endl;
				continue;
			}

			stack<int> st;
			while(S!=G){
				st.push(G);
				G = P[S][G];
			}

			cout << B[S][0];
			while(!st.empty()){
				cout << ' ' << B[st.top()][0];
				st.pop();
			}
			cout << endl;
		}
	}



	return 0;

}

C++: #include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

struct Edge {
	int to;
	double d;
	Edge (int _t, double _d) : to(_t), d(_d) {}
};

bool operator > (const Edge& e1, const Edge& e2) {
	if (e1.d > e2.d) return true;
	return false;
}

struct Buil {
	int id;
	double x, y;
	Buil (int _i, double _x, double _y) : id(_i), x(_x), y(_y) {}
};

double builDist(const Buil& b1, const Buil& b2) {
	return sqrt((b1.x - b2.x)*(b1.x - b2.x) + (b1.y - b2.y)*(b1.y - b2.y));
}

int n, m;
vector< Buil > buils;
vector< vector<Edge> > G;

double INF = 1e9;
double dist[1010];
int prev[1010];

void dks(int s, int g) {
	fill(dist, dist + 1010, INF);
	memset(prev, -1, sizeof(prev));	
	
	priority_queue<Edge, vector<Edge>, greater<Edge> > que;
	que.push(Edge(s, 0));
	dist[s] = 0;
	
	while (!que.empty()) {
		Edge e1 = que.top(); que.pop();
		
		for (int i = 0; i < G[e1.to].size(); i++) {
			Edge e2 = G[e1.to][i];
			
			if (dist[e2.to] > e1.d + e2.d) {
				dist[e2.to] = e1.d + e2.d;
				prev[e2.to] = e1.to;
				que.push(Edge(e2.to, e1.d + e2.d));
			}
		}
	}
	
	if (dist[g] == INF) cout << "NA" << endl;
	else {
		vector<int> path;
		path.push_back(g);
		int cnt = 0;
		for (int u = prev[g]; u != -1; u = prev[u]) {
			path.push_back(u);
		}
		int size = (int)path.size();
		for (int i = 0; i < size - 1; i++) {
			cout << path[size - 1 - i] << " ";
		}
		cout << path[0] << endl;
	}	
}

int main() {
	while (1) {
		cin >> n; if (n == 0) break;
		
		buils.clear();
		for (int i = 0; i < n; i++) {
			int b, x, y; cin >> b >> x >> y;
			buils.push_back(Buil(b, x, y));
		}
		
		G.assign(1010, vector<Edge>());
		for (int i = 0; i < (int)buils.size(); i++) {
			for (int j = i + 1; j < (int)buils.size(); j++) {
				double d = builDist(buils[i], buils[j]);
				if (d > 50) continue;
				G[buils[i].id].push_back(Edge(buils[j].id, d));
				G[buils[j].id].push_back(Edge(buils[i].id, d));
			}
		}
		
		cin >> m;
		for (int i = 0; i < m; i++) {
			int s, g; cin >> s >> g;
			dks(s, g);
		}
	}
	
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

int main() {
	bool judge = true;
	while (judge) {
		int n, m;
		int b[n], x[n], y[n], s[m], g[m];
		cin >> n;
		if (n == 0) {
			judge = false;
			return 0;
		}
		for (int i = 0; i < n; i++) cin >> b[i] >> x[i] >> y[i];
		cin >> m;
		for (int i = 0; i < m; i++) cin >> s[i] >> g[i];
		const int INF = 1000000;
		int dp[n][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					dp[j][k] = INF;
				}
			}
			dp[s[i] - 1][0] = 0;
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n - 1; k++) {
					if (dp[j][k] != INF) {
						for (int l = 0; l < n; l++) {
							int p = abs(x[j] - x[l]) * abs(x[j] - x[l]);
							int q = abs(y[j] - y[l]) * abs(y[j] - y[l]);
							if (l != j && p + q <= 2500) {
								dp[l][k + 1] = min(dp[l][k + 1], dp[j][k] + 1);
							}
						}
					}
				}
			}
			int t = 0;
			for (int j = 0; j < n; j++) {
				if (dp[g[i] - 1][j] != INF) {
					t = dp[g[i] - 1][j];
					break;
				}
			}
			if (t == 0) {
				cout << "NA" << endl;
			}
			else {
				int ans[t + 1] = { 0 };
				ans[t] = g[i] - 1;
				for (int j = t; j > 0; j--) {
					for (int k = 0; k < n; k++) {
						int p = abs(x[ans[j]] - x[k]) * abs(x[ans[j]] - x[k]);
						int q = abs(y[ans[j]] - y[k]) * abs(y[ans[j]] - y[k]);
						if (dp[k][j - 1] == j - 1 && p + q <= 2500) {
							ans[j - 1] = k;
							break;
						}
					}
				}
				for (int j = 0; j <= t; j++) {
					cout << ans[j] + 1 << ' ';
					if (j == t) {
						cout << endl;
					}
				}
			}
		}
	}
}