글 읽기 - 1753 - 파이썬, 다익스트라, 우선순위큐 사용 시간초과

plog 3년 전 0

input()도 sys.stdin으로 바꿔서 실행해봤는데 시간초과가 뜹니다.

여기서 더 최적화할 부분이 있을까요 고수님들...?

from heapq import heappush, heappop
import time
import sys

# start_time = time.time()
vertex_n, edge_n = map(int, sys.stdin.readline().split())
start = int(input())

graph = [[] for i in range(vertex_n + 1)]
dist = [sys.maxsize] * (vertex_n + 1)

for _ in range(edge_n):
    start_vertex, destination_vertex, weight = map(
        int, sys.stdin.readline().split())
    graph[start_vertex].append((weight, destination_vertex))

q = []
heappush(q, (0, start))
dist[start] = 0
while q:
    curr_weight, curr_vertex = heappop(q)

    if dist[curr_vertex] < curr_weight:
        continue

    for w, v in graph[curr_vertex]:
        cost = dist[curr_vertex] + w
        if cost < dist[v]:
            dist[v] = cost
            heappush(q, (w, v))

for i in range(1, vertex_n + 1):
    if dist[i] == sys.maxsize:
        print("INF")
    else:
        print(dist[i])
# end_time = time.time()
# print(f"ms: {end_time - start_time}")

djm03178 3년 전 0

https://www.acmicpc.net/board/... 의 4-3번에 해당됩니다.

plog 3년 전 0

아 감사합니다..!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1753 - 파이썬, 다익스트라, 우선순위큐 사용 시간초과

plog 3년 전 0

djm03178 3년 전 0

plog 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말