幅優先探索

C - Cat Snuke and a Voyage

O(N)

from asyncio import QueueFull
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, M = list(map(int, input().split()))
    G = []

    for _ in range(N):
        G.append([])

    for i in range(M):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    dist = []
    for _ in range(N):
        dist.append(-1)

    Q = deque()
    Q.append(0)
    dist[0] = 0

    while len(Q) > 0:
        i = Q.popleft()
        for j in G[i]:
            if dist[j] == -1:
                dist[j] = dist[i] + 1
                Q.append(j)

    if dist[N-1] == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

# エントリポイント
if __name__ == '__main__':
    main()

heapqを使用し、ダイクストラに対応。

from asyncio import QueueFull
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, M = list(map(int, input().split()))
    G = []

    for _ in range(N):
        G.append([])

    for i in range(M):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    dist = []
    done = []
    for _ in range(N):
        dist.append(-1)
        done.append(False)

    Q = []
    heapq.heappush(Q, (0, 0))
    dist[0] = 0

    while len(Q) > 0:
        d, i = heapq.heappop(Q)
        
        if done[i]:
            continue
        done[i] = True

        for j in G[i]:
            x = 1
            if dist[j] == -1 or dist[j] > dist[i] + x:
                dist[j] = dist[i] + x
                heapq.heappush(Q, (dist[j], j))

    if dist[N-1] == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

# エントリポイント
if __name__ == '__main__':
    main()

D - 単一始点最短経路問題

O(N)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, M = list(map(int, input().split()))
    G = []
    dist = []
    done = []

    for _ in range(N):
        G.append([])
        dist.append(-1)
        done.append(False)

    for _ in range(M):
        u, v, c = list(map(int, input().split()))
        G[u].append((v, c))

    Q = []
    heapq.heappush(Q, (0, 0))
    dist[0] = 0

    while len(Q) > 0:
        d, i = heapq.heappop(Q)
        if done[i]:
            continue
        done[i] = True
        for j, c in G[i]:
            if dist[j] == -1 or dist[j] > dist[i] + c:
                dist[j] = dist[i] + c
                heapq.heappush(Q, (dist[j], j))

    print(dist[N-1])

# エントリポイント
if __name__ == '__main__':
    main()