[알고리즘] 백준 1504 - 특정한 최단 경로

문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

풀이

어쩌다보니 오늘은 다 최단경로 알고리즘 문제... ! 이거는 예전에 풀었던 문제고, 아까 다익스트라를 풀었어서 바로 풀었다.

처음엔 간선이 양방향인데 단방향으로만 추가해줘서 틀렸습니다가 떴고,

두 번째엔 1e9 부분에서 -1을 출력해줘야 하는데 그 부분에서 ==과 >= 처리를 잘못해서 틀렸습니다를 몇 번 겪고난 후에 ^ __ ^ 정답을 띄울 수 있었다ㅎㅎ 마지막 틀렸습니다는 그냥 실험...겸 한 번 해봤다.

아주 알록달록한 채점 현황표 ㅎ....ㅎ

 

 

정답 코드

import heapq
import sys
input = sys.stdin.readline

n,e = map(int,input().split())

graph = [[] for _ in range(n+1)]

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



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

def djikstra(s,e):
    distance = [1e9 for _ in range(n+1)]
    q = []
    heapq.heappush(q,(0,s))
    distance[s] = 0
    
    while q:
        d,v = heapq.heappop(q)
        if distance[v] < d:
            continue
        for v1,c1 in graph[v]:
            if distance[v1] > distance[v] + c1:
                distance[v1] = distance[v] + c1
                heapq.heappush(q,(distance[v1],v1))
    return distance[e]

tmp_result_1 = djikstra(1,v1) + djikstra(v1,v2) + djikstra(v2,n)
tmp_result_2 = djikstra(1,v2) + djikstra(v2,v1) + djikstra(v1,n)

result = min(tmp_result_1,tmp_result_2)
if result >= 1e9:
    print(-1)
else:
    print(result)