글 읽기 - 이 문제를 보면 heap을 사용해야된다는 느낌이 오시나요?

ehfkswl 3년 전 0

처음에 리스트로 작성해서 답만 맞췄다가, 다른 답안들 보며 heap을 사용하고

input()을 바꿔 sys.stdin.readline으로 바꾸어 시간초과를 해결했습니다.

알고리즘은 맞았는데 효율성 부분(heap 사용이나, readline 을 효율성으로 봐야 할지 잘 모르겠지만)이 틀렸다면 잘못된 코드 인가요?

import math
import heapq
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V+1)]
heap = []

for _ in range(E):
    v1, v2, c = map(int, input().split())
    graph[v1].append([c, v2])

cost = [math.inf] * (V+1)
cost[start] = 0

heapq.heappush(heap, [0, start])
while(heap):
    prev_cost, node = heapq.heappop(heap)
    for next_cost, vertex in graph[node]:
        if next_cost+prev_cost < cost[vertex]:
            cost[vertex] = next_cost+prev_cost
            heapq.heappush(heap, [next_cost + prev_cost, vertex])

for i in range(1, len(cost)):
    if cost[i] != math.inf:
        print(cost[i])
    else:
        print("INF")

Green55 3년 전 0

단순히 heap을 쓰는 문제라기보다는 다익스트라 알고리즘이라는 유명한 최단경로 알고리즘을 쓰는 문제입니다.

스스로 생각해서 풀 수 있는 문제는 아닌 것 같고, 다들 따로 공부를 하고 푸는 것 같습니다.

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

문제

문제

출처

ICPC

이 문제를 보면 heap을 사용해야된다는 느낌이 오시나요?

ehfkswl 3년 전 0

Green55 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말