[BOJ] 14618 - 총깡총깡

[백준] 14618 - 총깡총깡

문제 이해에 가장 노력을 쏟아야 하는 문제다.

풀이

다익스트라로 진서네 집에서 출발해 다른 집들까지 도달하는 거리를 모두 구하고, A그룹과 B그룹의 합을 각각 구해 최솟값을 출력한다.

소스코드

import heapq

INF = 999999999

n, m = map(int, input().split())
j = int(input())
k = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

cost =[[] for i in range(n+1)]

for i in range(m):
    x, y, z = map(int, input().split())
    cost[x].append((z,y))
    cost[y].append((z,x))

pq = []
dist = [INF for _ in range(n+1)]
dist[j] = 0

ck = [False for i in range(n+1)]
heapq.heappush(pq, (0, j))

while pq:
    c, here = heapq.heappop(pq)
    for d, node in cost[here]:
        if dist[node] > c + d:
            dist[node] = c + d
            heapq.heappush(pq, (dist[node], node))

A_mn = INF
B_mn = INF

for i in A:
    A_mn = min(A_mn, dist[i])

for i in B:
    B_mn = min(B_mn, dist[i])

if A_mn == B_mn == INF:
    print(-1)
elif A_mn <= B_mn:
    print("A")
    print(A_mn)
else:
    print("B")
    print(B_mn)