[BOJ/백준] 1753 최단경로 (실패사례도 있음)

import collections

N,M = map(int,input().split())
start = int(input())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    n1,n2,d = map(int,input().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node = start

while True:
    visited[node] = False
    for ind,dis in graph[node]:
        distance[ind] = min(distance[ind],distance[node]+dis)
    next_node = -1
    next_min_distance = INF
    for ind in range(N+1):
        if visited[ind] and next_min_distance > distance[ind]:
            next_min_distance = distance[ind]
            next_node = ind
    if next_node != -1:
        node = next_node
    else:
        break

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

평소에 하던 다익스트라 문제였고, 평상시 하던대로 로직을 짜서 실행시켰다 하지만 시간초과라는 결과가 나왔다.

 

 

 

평소에 heapq라는 라이브러리가 익숙치 않아서 쓰지 않았던 heapq를 썼다. heapq를 써서 문제를 풀었다.

 

import heapq
import sys
N,M = map(int,input().split())
start = int(input())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    n1,n2,d = map(int,sys.stdin.readline().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node_list = []
heapq.heappush(node_list,(0,start))

while node_list:
    current_distance,node= heapq.heappop(node_list)
    visited[node] = True
    if distance[node]<current_distance:
        continue
    for next_node,next_dis in graph[node]:
        if visited[next_node]:
            temp_distance = current_distance + next_dis
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(distance[next_node],next_node))

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

heapq를 썼을시에는 통과가 가능했다.

 

 

시간복잡도는 heapq가 더 빠르니, heapq에 대해서도 공부해야겠다.