1504 특정한 최단 경로 python

휴대용치즈 2023. 1. 8. 16:22

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

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

문제 접근

다익스트라 알고리즘

특정한 두 경로를 무조건 지나가야한다.

가까운 경로를 먼저 지나려고 한다면 이런 반례가 있다.

1에서 4까지 가는데 특정한 경로 2,3을 지나야한다고 하면,

1->3으로 갔다가 3->2로 이동하고 다시 2->4로 이동하는데 더 멀리 둘러가게된다.

결론은 v1, v2중 어딜 먼저 가야할지 정해두고 풀 수가 없다.

그래서 v1을 먼저가는 경우와 v2를 먼저가는 경우 둘 다 구해야 한다.

그리고 78%에서 틀리는 경우는 출력의 -1을 무시했기 때문.

그러한 경로가 없을 때에는 -1을 출력한다.

1번 틀렸다ㅜㅜ

코드

import heapq
import sys
input = sys.stdin.readline

"""


"""

N, E = map(int,input().split())
graph = [[] for i in range(N+1)]
for i in range(E):
    a, b, c = map(int,input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))
v1, v2 = map(int,input().split())

def dijkstra(start):
    heap = [(0, start)]
    INF = float('inf')
    dp = [INF] * (N+1)
    dp[start] = 0

    while heap:
        w1, s = heapq.heappop(heap)

        if dp[s] < w1:
            continue

        for w2, e in graph[s]:
            if w1 + w2 < dp[e]:
                dp[e] = w1 + w2
                heapq.heappush(heap, (w1 + w2, e))
    
    return dp

ans1 = dijkstra(1)
ans2 = dijkstra(v1)
ans3 = dijkstra(v2)
ans = min(ans1[v1] + ans2[v2] + ans3[N], ans1[v2] + ans3[v1] + ans2[N])
print(ans if ans<float('inf') else -1)

64248

392