[백준23793] / 두 단계 최단 경로 1 - 다익스트라

 

백준23793

 

 

푼 날짜 : 2024.11.15

푼 문제 : [23793] / 두 단계 최단 경로 1

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

 

1) (X -> Y) + (Y -> Z) 계산

2) X -> Z 계산 (이때 Y는 지나가면 안된다. )

 

따라서 아래와 같이 계산을 해서 답을 구했다.

 

XY = dijkstra(X) # X -> Y 계산
YZ = dijkstra(Y) # Y -> Z 계산

 

XZ = dijkstra(X, True) # X -> Z (Y는 지나가면 안됨)

 

그리고 답이 INF인 경우 -1을 출력했다.

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline
INF = float("INF")

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

X, Y, Z = map(int, input().split())

def dijkstra(num, check = False):
    heap = [(0, num)]
    dist = [INF for _ in range(N+1)]
    dist[num] = 0

    while heap:
        now_cost, now_node = heapq.heappop(heap)
        if dist[now_node] < now_cost: continue

        for next, cost in graph[now_node]:
        	# Y 를 지나가면 안되는 경우
            if check and (next == Y): continue
            
            all_cost = now_cost + cost

            if dist[next] > all_cost:
                dist[next] = all_cost
                heapq.heappush(heap, (all_cost, next))

    return dist

XY = dijkstra(X) # X -> Y 계산
YZ = dijkstra(Y) # Y -> Z 계산
XZ = dijkstra(X, True) # X -> Z (Y는 지나가면 안됨)

# 지나갈 수 없는 경우 -1 출력을 위함
ans = XY[Y]+YZ[Z] if XY[Y]+YZ[Z] != INF else -1
ans2 = XZ[Z] if XZ[Z] != INF else -1

print(ans, ans2)

 

 

이 정도면 거의 다익스트라 중독 !!!!