Softeer 지우는 소수를 좋아해 (난이도 4)

정답 코드

import sys
import heapq
N, M = map(int, sys.stdin.readline().split())
node = [[] for i in range(N + 1)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split()) 
    node[a].append([b, c])
    node[b].append([a, c])

dest = [987654321 for i in range(N + 1)]

def dijkstra(start):
    dest[start] = 0
    heap = [[0, start]]
    while len(heap):
        curr = heapq.heappop(heap)
        if dest[curr[1]] < curr[0]:
            continue
        for n in node[curr[1]]:
            nex = n[0]
            nexdist = max(curr[0], n[1])
            if nexdist < dest[nex]:
                dest[nex] = nexdist
                heapq.heappush(heap, [nexdist, nex])
    
dijkstra(1)
for i in range(dest[N] + 1, dest[N] * 2):
    if i % 2 == 0:
        continue
    pn = True
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            pn = False
            break
    if pn:
        print(i)
        break

알고리즘 유형

다익스트라