Problem:


スパイダー人

正義のヒーロー「スパイダー人」は、腕からロープを出してビルからビルへ飛び移ることができます。しかし、ロープが短いので自分からの距離が 50 以下のビルにしか移動できません。それより遠くのビルに移動するには、一旦別のビルに飛び移らなくてはなりません。

ビルの数 n、n 個のビルの情報、スパイダー人の移動開始位置及び目的地を入力とし、その移動の最短経路を出力するプログラムを作成してください。どのようにビルを経由しても目標のビルに移動できない場合は NA と出力してください。各ビルは点として扱い、最短距離で移動するビルの経由方法が２つ以上存在することはないものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下の形式で与えられます。

n
b1 x1 y1
b2 x2 y2
:
bn xn yn
m
s1 g1
s2 g2
:
sm gm

１行目にビルの数 n (1 ≤ n ≤ 100)、続く n 行に i 番目のビルのビル番号 bi (1 ≤ bi ≤ n)、そのビルのx座標とy座標を表す整数 xi, yi (-1000 ≤ xi, yi ≤ 1000) が空白区切りで与えられます。

続く行に移動情報の個数 m (1 ≤ m ≤ 100)、続く m 行にi  番目の移動情報が与えられます。各移動情報として、移動を開始するビルの番号 si と目的地ビルの番号 gi が空白区切りで与えられます。

データセットの数は 10 を超えません。

Output

入力データセットごとに次の形式で出力します。

i 行目に i 番目の移動情報に対する経路または NA を１行に出力します。各経路は以下の形式で出力します。

si bri1 bri2 ... gi

brij は i 番目の移動情報における、j 番目に経由するビルの番号を表します。

Sample Input

4
1 0 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0

Output for the Sample Input

1 2 3
NA
1 3 9 20 11 6 22



Sample input:
4
1 0 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0


Sample output:
1 2 3
NA
1 3 9 20 11 6 22

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

from heapq import heappush, heappop

def solve(s):
    if s in memo:
        return memo[s]
    que = [(0, s)]
    dist = [10**18]*N
    prev = [None]*N
    dist[0] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for d, w in G[v]:
            if c + d < dist[w]:
                dist[w] = c + d
                prev[w] = v
                heappush(que, (c+d, w))
    memo[s] = prev
    return prev


while 1:
    N = int(readline())
    if N == 0:
        break
    P = [None]*N
    X = [0]*N; Y = [0]*N
    for i in range(N):
        b, x, y = map(int, readline().split())
        P[b-1] = complex(x, y)
    G = [[] for i in range(N)]
    for i in range(N):
        pi = P[i]
        for j in range(i+1, N):
            d = abs(pi - P[j])
            if d <= 50:
                G[i].append((d, j))
                G[j].append((d, i))

    memo = {}
    M = int(readline())
    for i in range(M):
        s, g = map(int, readline().split()); s -= 1; g -= 1
        prev = solve(s)
        if prev[g] is None:
            write("NA\n")
            continue
        res = [str(g+1)]
        while s != g:
            g = prev[g]
            res.append(str(g+1))
        res.reverse()
        write(" ".join(res))
        write("\n")

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

from heapq import heappush, heappop

def solve(s):
    if s in memo:
        return memo[s]
    que = [(0, s)]
    dist = [10**18]*N
    prev = [None]*N
    dist[0] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for d, w in G[v]:
            if c + d < dist[w]:
                dist[w] = c + d
                prev[w] = v
                heappush(que, (c+d, w))
    memo[s] = prev
    return prev


while 1:
    N = int(readline())
    if N == 0:
        break
    P = [None]*N
    X = [0]*N; Y = [0]*N
    for i in range(N):
        b, x, y = map(int, readline().split())
        P[b-1] = complex(x, y)
    G = [[] for i in range(N)]
    for i in range(N):
        pi = P[i]
        for j in range(i+1, N):
            d = abs(pi - P[j])
            if d < 50 + 1e-5:
                G[i].append((d, j))
                G[j].append((d, i))

    memo = {}
    M = int(readline())
    for i in range(M):
        s, g = map(int, readline().split()); s -= 1; g -= 1
        prev = solve(s)
        if prev[g] is None:
            write("NA\n")
            continue
        res = [str(g+1)]
        while s != g:
            g = prev[g]
            res.append(str(g+1))
        res.reverse()
        write(" ".join(res))
        write("\n")

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

from heapq import heappush, heappop

def solve(s):
    if s in memo:
        return memo[s]
    que = [(0, s)]
    dist = [10**18]*N
    prev = [None]*N
    dist[0] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for d, w in G[v]:
            if c + d < dist[w]:
                dist[w] = c + d
                prev[w] = v
                heappush(que, (c+d, w))
    memo[s] = prev
    return prev


while 1:
    N = int(readline())
    if N == 0:
        break
    P = [None]*N
    X = [0]*N; Y = [0]*N
    for i in range(N):
        b, x, y = map(int, readline().split())
        P[b-1] = complex(x, y)
    G = [[] for i in range(N)]
    for i in range(N):
        pi = P[i]
        for j in range(i+1, N):
            d = (pi - P[j]) * (pi - P[j]).conjugate()
            if d.real <= 2500:
                d = abs(pi - P[j])
                G[i].append((d, j))
                G[j].append((d, i))

    memo = {}
    M = int(readline())
    for i in range(M):
        s, g = map(int, readline().split()); s -= 1; g -= 1
        prev = solve(s)
        if prev[g] is None:
            write("NA\n")
            continue
        res = [str(g+1)]
        while s != g:
            g = prev[g]
            res.append(str(g+1))
        res.reverse()
        write(" ".join(res))
        write("\n")

Submission status: Wrong Answer

Solution code:
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  d1, i1 = distance.pop(0)
  if i1 == g:
    return 1

  f = 0
  for i, e in enumerate(distance):
    d2, i2 = e[0], e[1]
    dd = segment[(i1, i2)]
    if dd > 50:
      continue
    f = 1
    if d1 + dd < d2:
      distance[i][0] = d1 + dd
      Path[i2]=i1
  if f:
    return solve(sorted(distance), g)
  return 0

def PathOut(g,s):
  x = []
  while g != s:
    x.append(Name[g])
    g = Path[g]
  x.append(Name[s])
  for e in x[1:][::-1]:
    print e,
  print x[0]
  return

while 1:
  n = int(raw_input())
  if n == 0:
    break
  Name, segment = BldIn(n)
  Path = {}

  m = int(raw_input())
  for _ in [0] * m:
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[1e9, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g):
      PathOut(g, s)
    else:
      print "NA"

Submission status: Wrong Answer

Solution code:
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  d1, i1 = distance.pop(0)
  if i1 == g:
    return 1

  x1=[]
  x2=[]
  for i, e in enumerate(distance):
    d2, i2 = e[0], e[1]
    dd = segment[(i1, i2)]
    if dd > 50:
      x2.append(e)
      continue
    x1.append(e)
    if d1 + dd < d2:
      distance[i][0] = d1 + dd
      Path[i2] = i1
  if x1:
    return solve(sorted(x1)+x2, g)
  return 0

def PathOut(g, s):
  x = [Name[g]]
  while g != s:
    g = Path[g]
    x.append(Name[g])
  for e in x[1:][::-1]:
    print e,
  print x[0]
  return

while 1:
  n = int(raw_input())
  if n == 0:
    break
  Name, segment = BldIn(n)

  m = int(raw_input())
  for _ in [0] * m:
    Path = {}
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[1e9, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g):
      PathOut(g, s)
    else:
      print "NA"

Submission status: Wrong Answer

Solution code:
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  d1, i1 = distance.pop(0)
  if i1 == g:
    return 1

  x1=[]
  x2=[]
  for i, e in enumerate(distance):
    d2, i2 = e[0], e[1]
    dd = segment[(i1, i2)]
    if dd > 50:
      x2.append(e)
      continue
    if d1 + dd < d2:
      distance[i][0] = d1 + dd
      Path[i2] = i1
    x1.append(distance[i])
  if x1:
    return solve(sorted(x1)+x2, g)
  return 0

def PathOut(g, s):
  x = [Name[g]]
  while g != s:
    g = Path[g]
    x.append(Name[g])
  for e in x[1:][::-1]:
    print e,
  print x[0]
  return

while 1:
  n = int(raw_input())
  if n == 0:
    break
  Name, segment = BldIn(n)

  m = int(raw_input())
  for _ in [0] * m:
    Path = {}
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[1e9, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g):
      PathOut(g, s)
    else:
      print "NA"

Submission status: Wrong Answer

Solution code:
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  D = enumerate(distance)
  for i1, e1 in D:
    d1, p1 = e1
    if d1 != inf and p1 == g: return 1
    x1=[]
    x2=[]
    for i2, e2 in D:
      d2, p2 = e2
      if i1==i2: continue
      dd = segment[(p1, p2)]
      if dd > 50:
        x2.append(e2)
        continue
      if d1 + dd < d2:
        distance[i2][0] = d1 + dd
        Path[p2] = p1
      x1.append(distance[i2])
    if x1: return solve(sorted(x1)+x2, g)
  return 0

def PathOut(g, s):
  x = [Name[g]]
  while g != s:
    g = Path[g]
    x.append(Name[g])
  for e in x[1:][::-1]: print e,
  print x[0]
  return

inf = 1e9
while 1:
  n = int(raw_input())
  if n == 0: break
  Name, segment = BldIn(n)

  m = int(raw_input())
  for _ in [0] * m:
    Path = {}
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[inf, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g): PathOut(g, s)
    else: print "NA"

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
import math

# 再帰の最大回数を設定
LIMIT = 100000
sys.setrecursionlimit(LIMIT)


EPS = 1e-10
INF = 99999999

def main():
    # 入力
    while True:
        try:
            n = int(raw_input())
            bills = [map(int, raw_input().split()) for x in xrange(n)]
            m = int(raw_input())
            moves = [map(int, raw_input().split()) for x in xrange(m)]
            for x in computeShortestPath(bills, moves):
                print(x)

        except:
            break

def computeShortestPath(bills, moves):
    dic = makeDic(bills)
    return [computeShortestPath_(dic, x) for x in moves]

def computeShortestPath_(dic, move):
    # 辺のコストを計算
    cost = {(move[0], x):makeLength(dic[x], dic[move[0]]) for x in dic}

    used = {}                   # 既に辿っているかどうか
    mincost = {x:INF for x in dic}
    mincost[move[0]] = 0        # 最短距離
    prev = {}                    # 最短の際の前のノード

    def dijkstra(move):
        used[move[0]] = True    # ノードを既訪に設定
        cost.update({(move[0], x):makeLength(dic[x], dic[move[0]]) for x in dic})                        # 現在のノードからの距離を算出

        # 現在のノードから訪れることのできるノードを抽出
        next_moves = filter(lambda x:canMove(cost[(move[0], x)]), dic)
        # 既訪ノードを削除
        next_moves = filter(lambda x:x not in used, next_moves)

        # 全てのノードに訪れている
        if len(next_moves) == 0:
            return
        else:

            # 最短距離を設定
            for x in next_moves:
                if mincost[x] > cost[(move[0], x)] + mincost[move[0]]:
                    mincost[x] = cost[(move[0], x)] + mincost[move[0]]
                    prev[x] = move[0]
                else:
                    pass
            # 未訪ノード
            yet_node = filter(lambda x:x not in used, dic)

            # 未訪ノードから最小コストのものを抽出
            min_bill = min(yet_node, key=lambda x:mincost[x])

            # 次のノードについて再帰
            return dijkstra((min_bill, move[1]))

    dijkstra(move)
    if not mincost[move[1]] == INF:
        return keiro(prev, move)
    else:
        return "NA"

def keiro(prev, move):
    node = move[1]
    path = [move[1]]
    while node != move[0]:
        node = prev[node]
        path.append(node)
    return reduce(lambda a, x: str(a) + " " + str(x), path[::-1])

def makeLength(p1, p2):
    return math.sqrt(((p1[0] - p2[0]) **2 + (p1[1] - p2[1]) ** 2))

def canMove(length):
    if length <= 50 + EPS:
        return True
    else:
        return False

def makeDic(bills):
    dic = {}
    for x in bills:
        dic[x[0]] = (x[1], x[2])

    return dic

def test():
    bills = [   [1 ,0 ,0],
                [2, 30, 0],
                [3, 60, 40],
                [4, 0, 60]]
    moves = [[1, 3], [1, 4]]
    for x in computeShortestPath(bills, moves):
        print x

if __name__=='__main__':
    # test()
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
import math

# 再帰の最大回数を設定
LIMIT = 100000
sys.setrecursionlimit(LIMIT)

EPS = 1e-10
INF = 99999999

def main():
    # 入力
    while True:
        n = int(raw_input())
        if n == 0:
            break
        bills = [map(int, raw_input().split()) for x in xrange(n)]
        m = int(raw_input())
        moves = [map(int, raw_input().split()) for x in xrange(m)]
        for x in computeShortestPath(bills, moves):
            print(x)

def computeShortestPath(bills, moves):
    dic = makeDic(bills)
    return [computeShortestPath_(dic, x) for x in moves]

def computeShortestPath_(dic, move):
    # 辺のコストを計算
    cost = {(move[0], x):makeLength(dic[x], dic[move[0]]) for x in dic}

    used = {}                   # 既に辿っているかどうか
    mincost = {x:INF for x in dic}
    mincost[move[0]] = 0        # 最短距離
    prev = {}                    # 最短の際の前のノード

    def dijkstra(move):
        used[move[0]] = True    # ノードを既訪に設定
        cost.update({(move[0], x):makeLength(dic[x], dic[move[0]]) for x in dic})                        # 現在のノードからの距離を算出

        # 現在のノードから訪れることのできるノードを抽出
        next_moves = filter(lambda x:canMove(cost[(move[0], x)]), dic)
        # 既訪ノードを削除
        next_moves = filter(lambda x:x not in used, next_moves)

        # 全てのノードに訪れている
        if len(next_moves) == 0:
            return
        else:

            # 最短距離を設定
            for x in next_moves:
                if mincost[x] > cost[(move[0], x)] + mincost[move[0]]:
                    mincost[x] = cost[(move[0], x)] + mincost[move[0]]
                    prev[x] = move[0]
                else:
                    pass
            # 未訪ノード
            yet_node = filter(lambda x:x not in used, dic)

            # 未訪ノードから最小コストのものを抽出
            min_bill = min(yet_node, key=lambda x:mincost[x])

            # 次のノードについて再帰
            return dijkstra((min_bill, move[1]))

    dijkstra(move)
    if not mincost[move[1]] == INF:
        return keiro(prev, move)
    else:
        return "NA"

def keiro(prev, move):
    node = move[1]
    path = [move[1]]
    while node != move[0]:
        node = prev[node]
        path.append(node)
    return reduce(lambda a, x: str(a) + " " + str(x), path[::-1])

def makeLength(p1, p2):
    return math.sqrt(((p1[0] - p2[0]) **2 + (p1[1] - p2[1]) ** 2))

def canMove(length):
    if length <= 50 + EPS:
        return True
    else:
        return False

def makeDic(bills):
    dic = {}
    for x in bills:
        dic[x[0]] = (x[1], x[2])

    return dic

def test():
    bills = [   [1 ,0 ,0],
                [2, 30, 0],
                [3, 60, 40],
                [4, 0, 60]]
    moves = [[1, 3], [1, 4]]
    for x in computeShortestPath(bills, moves):
        print x

if __name__=='__main__':
    # test()
    main()

Submission status: Wrong Answer

Solution code:
from collections import namedtuple, defaultdict
Point = namedtuple("Point", ["x", "y"])

def main():
    while True:
        n = input()
        if n == 0:
            break
        bldgs = {}
        for _ in xrange(n):
            b, x, y = map(int, raw_input().split())
            bldgs[b] = Point(x, y)
        graph = make_graph(bldgs)
        for _ in xrange(input()):
            sb, gb = map(int, raw_input().split())
            res = dijkstra(graph, sb, gb)
            if res is None:
                print "NA"
            else:
                print " ".join(map(str, reversed(res)))
        
def make_graph(bldgs):
    graph = defaultdict(list)
    for b1, p1 in bldgs.items():
        for b2, p2 in bldgs.items():
            if b1 == b2:
                continue
            weight = (p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2
            if weight > 2500:
                continue
            graph[b1].append((weight**0.5, b2,))
    return graph

def dijkstra(graph, start, goal):
    import heapq
    hq = [(w, b, start) for w, b in graph[start]]
    heapq.heapify(hq)
    pre = dict((k, None) for k in graph.keys())
    while len(hq) > 0:
        w, cb, pb = heapq.heappop(hq)
        if pre[cb] is not None:
            continue
        pre[cb] = pb
        if cb == goal:
            break
        for nw, nb in graph[cb]:
            heapq.heappush(hq, (nw+w, nb, cb))
    else:
        return None
    ret = [goal]
    while ret[-1] != start:
        ret.append(pre[ret[-1]])
    return list(reversed(ret))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155

"""
import sys
from sys import stdin
from math import sqrt
input = stdin.readline


def dijkstra(s, G):
    BLACK, GRAY, WHITE = 0, 1, 2
    d = [float('inf')] * 101
    color = [WHITE] * 101
    p = [-1] * 101

    d[s] = 0
    while True:
        mincost = float('inf')
        # ??\??????????????§??????????????¨?????????????????????u???????????????
        for i in range(101):
            if color[i] != BLACK and d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                mincost = d[i]
                u = i  # u??????????????????ID
        if mincost == float('inf'):
            break
        color[u] = BLACK  # ?????????u???S????±???????????????´???
        for v in range(101):
            if color[v] != BLACK and G[u][v] != float('inf'):
                # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                if d[u] + G[u][v] < d[v]:
                    d[v] = d[u] + G[u][v]
                    p[v] = u
                    color[v] = GRAY
    return d, p


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break

        G = [[float('inf')] * (100+1) for _ in range(100+1)]
        data = []
        for _ in range(n):
            b, x, y = map(int, input().split(' '))
            data.append([b, x, y])

        for i in range(n):
            b1, x1, y1 = data[i]
            for j in range(n):
                b2, x2, y2 = data[j]
                if b1 == b2:
                    continue
                dist = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if dist <= 50.0:
                    G[b1][b2] = dist
                    G[b2][b1] = dist

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().split(' '))
            if s == g:
                print(s)
                continue
            if (not 1<= s <= 100) or (not 1<= g <= 100):
                print('NA')
                continue
            d, p = dijkstra(s, G)
            if d[g] == float('inf'):
                print('NA')
            else:
                path = [g]
                while p[g] != s:
                    path.append(p[g])
                    g = p[g]
                path.append(s)
                rev = path[::-1]
                print(' '.join(map(str, rev)))


def main2(args):
    while True:
        n = int(input())
        if n == 0:
            break

        for _ in range(n):
            input()

        m = int(input())
        for _ in range(m):
            input()
            print('NA')


if __name__ == '__main__':
    main2(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155

"""
import sys
from sys import stdin
from math import sqrt
input = stdin.readline


def dijkstra(s, G):
    BLACK, GRAY, WHITE = 0, 1, 2
    d = [float('inf')] * 101
    color = [WHITE] * 101
    p = [-1] * 101

    d[s] = 0
    while True:
        mincost = float('inf')
        # ??\??????????????§??????????????¨?????????????????????u???????????????
        for i in range(101):
            if color[i] != BLACK and d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                mincost = d[i]
                u = i  # u??????????????????ID
        if mincost == float('inf'):
            break
        color[u] = BLACK  # ?????????u???S????±???????????????´???
        for v in range(101):
            if color[v] != BLACK and G[u][v] != float('inf'):
                # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                if d[u] + G[u][v] < d[v]:
                    d[v] = d[u] + G[u][v]
                    p[v] = u
                    color[v] = GRAY
    return d, p


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break

        G = [[float('inf')] * (100+1) for _ in range(100+1)]
        data = []
        for _ in range(n):
            b, x, y = map(int, input().split(' '))
            data.append([b, x, y])

        for i in range(n):
            b1, x1, y1 = data[i]
            for j in range(n):
                b2, x2, y2 = data[j]
                if b1 == b2:
                    continue
                dist = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if dist <= 50.0:
                    G[b1][b2] = dist
                    G[b2][b1] = dist

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().split(' '))
            if s == g:
                print(s)
                continue
            if (not 1<= s <= 100) or (not 1<= g <= 100):
                print('NA')
                continue
            d, p = dijkstra(s, G)
            if d[g] == float('inf'):
                print('NA')
            else:
                path = [g]
                while p[g] != s:
                    path.append(p[g])
                    g = p[g]
                path.append(s)
                rev = path[::-1]
                print(' '.join(map(str, rev)))


def main2(args):
    while True:
        n = int(input())
        if n == 0:
            break

        for _ in range(n):
            input()

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().strip().split(' '))
            print('NA')


if __name__ == '__main__':
    main2(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155

"""
import sys
from sys import stdin
from math import sqrt
input = stdin.readline


def dijkstra(s, G):
    BLACK, GRAY, WHITE = 0, 1, 2
    d = [float('inf')] * 101
    color = [WHITE] * 101
    p = [-1] * 101

    d[s] = 0
    while True:
        mincost = float('inf')
        # ??\??????????????§??????????????¨?????????????????????u???????????????
        for i in range(101):
            if color[i] != BLACK and d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                mincost = d[i]
                u = i  # u??????????????????ID
        if mincost == float('inf'):
            break
        color[u] = BLACK  # ?????????u???S????±???????????????´???
        for v in range(101):
            if color[v] != BLACK and G[u][v] != float('inf'):
                # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                if d[u] + G[u][v] < d[v]:
                    d[v] = d[u] + G[u][v]
                    p[v] = u
                    color[v] = GRAY
    return d, p


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break

        G = [[float('inf')] * (100+1) for _ in range(100+1)]
        data = []
        for _ in range(n):
            b, x, y = map(int, input().split(' '))
            data.append([b, x, y])

        for i in range(n):
            b1, x1, y1 = data[i]
            for j in range(n):
                b2, x2, y2 = data[j]
                if b1 == b2:
                    continue
                dist = sqrt((x1 - x2)**2 + (y1 - y2)**2)
                if dist <= 50.0:
                    G[b1][b2] = dist
                    G[b2][b1] = dist

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().strip().split(' '))
            if s == g:
                print(s)
                continue
            if (not 1<= s <= 100) or (not 1<= g <= 100):
                print('NA')
                continue
            d, p = dijkstra(s, G)
            if d[g] == float('inf'):
                print('NA')
            else:
                path = [g]
                while p[g] != s:
                    path.append(p[g])
                    g = p[g]
                path.append(s)
                rev = path[::-1]
                print(' '.join(map(str, rev)))


def main2(args):
    while True:
        n = int(input())
        if n == 0:
            break

        for _ in range(n):
            b, x, y = map(int, input().strip().split(' '))

        m = int(input())
        for _ in range(m):
            s, g = map(int, input().strip().split(' '))
            print('NA')


if __name__ == '__main__':
    main2(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
import math

def routing(s,g,route):
    ans=[]
    i=g
    while i!=-1:
        ans.append(i+1)
        i=route[i]
    return ans[::-1]

inf=100000
while True:
    n=input()
    if n==0:break
    L=[[inf]*n for i in range(n)]
    for i in range(n):
        L[i][i]=0
    B=[map(int,raw_input().split()) for i in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            ba,xa,ya=B[i]
            bb,xb,yb=B[j]
            ba,bb=ba-1,bb-1
            d=math.sqrt(pow(xa-xb,2)+pow(ya-yb,2))
            if d<=50:
                L[ba][bb]=L[bb][ba]=d

    m=input()
    for p in range(m):
        s,g=map(int,raw_input().split())
        print "NA"

Submission status: Accepted

Solution code:
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  for i1, e1 in enumerate(distance):
    d1, p1 = e1
    if d1 != inf and p1 == g:
      return 1
    x1=[]
    x2=[]
    for i2, e2 in enumerate(distance):
      d2, p2 = e2
      if i1==i2: continue
      dd = segment[(p1, p2)]
      if dd > 50:
        x2.append(e2)
        continue
      if d1 + dd < d2:
        distance[i2][0] = d1 + dd
        Path[p2] = p1
      x1.append(distance[i2])
    if x1:
      return solve(sorted(x1)+x2, g)
  return 0

def PathOut(g, s):
  x = [Name[g]]
  while g != s:
    g = Path[g]
    x.append(Name[g])
  for e in x[1:][::-1]:
    print e,
  print x[0]
  return

inf = 1e9
while 1:
  n = int(raw_input())
  if n == 0:
    break
  Name, segment = BldIn(n)

  m = int(raw_input())
  for _ in [0] * m:
    Path = {}
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[inf, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g):
      PathOut(g, s)
    else:
      print "NA"

Submission status: Accepted

Solution code:
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  for i1, e1 in enumerate(distance):
    d1, p1 = e1
    if d1 != inf and p1 == g: return 1
    x1=[]
    x2=[]
    for i2, e2 in enumerate(distance):
      d2, p2 = e2
      if i1==i2: continue
      dd = segment[(p1, p2)]
      if dd > 50:
        x2.append(e2)
        continue
      if d1 + dd < d2:
        distance[i2][0] = d1 + dd
        Path[p2] = p1
      x1.append(distance[i2])
    if x1: return solve(sorted(x1)+x2, g)
  return 0

def PathOut(g, s):
  x = [Name[g]]
  while g != s:
    g = Path[g]
    x.append(Name[g])
  for e in x[1:][::-1]: print e,
  print x[0]
  return

inf = 1e9
while 1:
  n = int(raw_input())
  if n == 0: break
  Name, segment = BldIn(n)

  m = int(raw_input())
  for _ in [0] * m:
    Path = {}
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[inf, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g): PathOut(g, s)
    else: print "NA"

Submission status: Accepted

Solution code:
from collections import namedtuple, defaultdict
Point = namedtuple("Point", ["x", "y"])

def main():
    while True:
        n = input()
        if n == 0:
            break
        bldgs = {}
        for _ in xrange(n):
            b, x, y = map(int, raw_input().split())
            bldgs[b] = Point(x, y)
        graph = make_graph(bldgs)
        for _ in xrange(input()):
            sb, gb = map(int, raw_input().split())
            res = dijkstra(graph, sb, gb)
            if res is None:
                print "NA"
            else:
                print " ".join(map(str, res))
        
def make_graph(bldgs):
    graph = defaultdict(list)
    for b1, p1 in bldgs.items():
        for b2, p2 in bldgs.items():
            if b1 == b2:
                continue
            weight = (p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2
            if weight > 2500:
                continue
            graph[b1].append((weight**0.5, b2,))
    return graph

def dijkstra(graph, start, goal):
    import heapq
    hq = [(w, b, start) for w, b in graph[start]]
    heapq.heapify(hq)
    pre = dict((k, None) for k in graph.keys())
    while len(hq) > 0:
        w, cb, pb = heapq.heappop(hq)
        if pre[cb] is not None:
            continue
        pre[cb] = pb
        if cb == goal:
            break
        for nw, nb in graph[cb]:
            heapq.heappush(hq, (nw+w, nb, cb))
    else:
        return None
    ret = [goal]
    while ret[-1] != start:
        ret.append(pre[ret[-1]])    
    return list(reversed(ret))

if __name__ == "__main__":
    main()