[백준18223] / 민준이와 마산 그리고 건우 - 다익스트라

 

백준18223

 

 

푼 날짜 : 2024.11.15

푼 문제 : [18223] / 민준이와 마산 그리고 건우

사용한 언어 : python

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

 

 

접근방식 :

두 개의 경로를 계산해서 계산 값이 일치한다면 "SAVE HIM" 아니라면 "GOOD BYE"를 출력했다.

 

1) 민준(1) -> 마산(V)

2) 민준(1)-> 건우(P) -> 마산(V)

 

 

 

코드 :

import sys
import heapq

V, E, P = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(V+1)]
for _ in range(E):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append((B, C))
    graph[B].append((A, C))

def dijkstra(num):
    heap = [(0, num)]
    dist = [float("INF") for _ in range(V+1)]
    dist[num] = 0

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

        for next, cost in graph[now_line]:
            all_cost = now_cost + cost

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

a = dijkstra(1) 
b = dijkstra(P)

# 마산으로 바로 가는 경우 최단거리
ans1 = a[V]
# 건우에게 갔다가 마산가는 경우 최단거리
ans2 = a[P] + b[V]

print("SAVE HIM" if ans1 == ans2 else "GOOD BYE")

 

 

다익스트라 푸는 재미에 빠져버렸다 :) !!