Submission

Score: 100

User: SnowAveNode

Problemset: รถยนต์ รถไฟ เรือเมล์ ลิเก ตำรวจ

Language: python

Time: 0.225 second

Submitted On: 2026-04-13 08:31:49

import sys, heapq
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
dist = [float('inf')]*(n+1)
car = False

for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
    if (u == 1 and v == n) or (u == n and v == 1):
        car = True

if car:
    tmp = [[] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, n+1):
            if j not in adj[i]:
                tmp[i].append(j)
    adj = tmp

pq = [(0, 1)]
dist[1] = 0
while pq:
    current_distance, u = heapq.heappop(pq)
    if current_distance > dist[u]: continue
    for v in adj[u]:
        if current_distance + 10*abs(u-v) < dist[v]:
            dist[v] = current_distance + 10*abs(u-v)
            heapq.heappush(pq, (dist[v], v))

print(dist[n] if dist[n] != float('inf') else -1)