[BOJ/python]1504번 특정한 최단 경로

백준 1504번 특정한 다익스트라 파이썬

문제 링크 - https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

특정한 다익스트라 문제다.

1. 풀이

1번 정점에서 N번 정점까지의 최단 경로를 구한다. 이 때 반드시 거쳐야 하는 두 개의 정점이 있다. 해당 정점을 v1,v2라고 하자. 경로의 방향은 1번 정점 → (v1,v2) → N번 정점으로 주어졌으므로 v1을 먼저 방문할 지 ,v2를 먼저 방문할 지만 결정하면 된다.

즉, 1→v1→v2→N 혹은 1→v2→v1→N 의 최단 경로를 구하고 비교하면 된다.

• 시작 지점을 입력값으로 하는 다익스트라 함수를 작성한다.
• 1, v1, v2 를 각각 넣고 각각의 노드에 대하여 최단 경로가 저장된 배열을 반환한다.
• 두 경로 중 작은 값을 출력한다.

2. 코드

#특정한 다익스트라
from heapq import heappop, heappush
maxCost= float('inf')

N, E = map(int,input().split())
G=[ [0 for _ in range(N+1)] for _ in range(N+1) ]
for _ in range(E):
    u,v,c = map(int,input().split())
    G[u][v]=c
    G[v][u]=c
v1, v2 = map(int,input().split())

def dijkstra(start):
    
    heap=[]
    heappush(heap, [0,start])
    
    visited=[-1 for _ in range(N+1)]
    dist = [maxCost for _ in range(N+1)]
    dist[start]=0                           
    while heap:
        cost, node = heappop(heap)
        
        if visited[node]!=1:
            visited[node]=1
            
            for next in range(1,N+1):
                if node!=next and visited[next]==-1 and G[node][next]!=0:
                    
                    if dist[next] >= G[node][next] + cost:
                        dist[next] = G[node][next] + cost
                        heappush(heap, [dist[next], next])
    
    return dist

dist_start, dist_v1, dist_v2 = dijkstra(1), dijkstra(v1), dijkstra(v2)

tmp1= dist_start[v1] + dist_v1[v2] + dist_v2[N]
tmp2= dist_start[v2] + dist_v2[v1] + dist_v1[N]

if tmp1==maxCost and tmp2==maxCost:
    print(-1)
else:
    print(min(tmp1,tmp2))