[백준] 1504 특정한 최단경로 파이썬

문제

https://www.acmicpc.net/status?user_id=cme10575&problem_id=1504&from_mine=1 

채점 현황

 

---

풀이

 

다익스트라로 푸는 문제였다.

1 -> v1 -> v2 -> n

1 -> v2 -> v1 -> n

주어진 조건에 따라 위 두 가지의 경로 중 짧은 것을 반환하면 됐다.

근데 분명 다익스트라 맞게 따라했는데, 나랑 거의 유사한 코드는 통과하고 나의 코드는 시간초과가 떠서

엄청 여러번 시도하며 뭐가 문제인지 찾아봤는데 결론부터 말하면 readline 때문이었다.

 

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

[Python 문법] 파이썬 입력 받기(sys.stdin.readline)

백준에선 입력반복문때문에 시초도 뜨는구나. .. ㅠㅠ

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, e = map(int, input().split())
g = [[] for _ in range(n + 1)]

for _ in range(e):
    a, b, w = map(int, input().split())
    g[a].append((b, w))
    g[b].append((a, w))

def dijkstra(st):
    dist = [INF] * (n + 1)
    dist[st] = 0
    q = [(0, st)]

    while q:
        wei, now = heapq.heappop(q)
        if dist[now] < wei:
            continue

        for i in g[now]:
            cost = wei + i[1]
            if cost < dist[i[0]]:  # 현재 노드를 거치는게 더 짧은 경우
                dist[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return dist

v1, v2 = map(int, input().split())

minFromSt = dijkstra(1)
minFromv1 = dijkstra(v1)
minFromv2 = dijkstra(v2)
#minFromEd = dijkstra(n)

case1 = minFromSt[v1] + minFromv1[v2] + minFromv2[n]
case2 = minFromSt[v2] + minFromv2[v1] + minFromv1[n]
res = min(case1, case2)

print(res if res < INF else -1)

 

 

 

참고

https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-1540-%ED%8A%B9%EC%A0%95%ED%95%9C%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C

[파이썬]백준 1504 특정한최단경로

 

https://velog.io/@nyanyanyong/알고리즘다익스트라

[알고리즘][python]다익스트라