1. 문제 설명

정기검진

2. 문제 분석

'다리'를 시작점으로 집과 병원을 이어줄 수 있다. 어느 다리에서 출발했을 때 최소 거리가 걸리는지 모르기 때문에 (그리고 집과 병원의 위치에 따라서 달라질 수 있기 때문에) 모든 다리를 시작점으로 사용해 다익스트라 알고리즘을 사용할 수 있다.

• (집+병원+다리)가 모두 노드로 사용된다는 점에서 다리-다리를 잇는 간선도 존재한다는 점에 주의.

3. 나의 풀이

import sys
import heapq
from collections import deque

INF = sys.maxsize
n, m, b, k, q = map(int, sys.stdin.readline().rstrip().split())
# 총 (n+m+b) 개 노드, k 개 간선
nodes = [[] for _ in range(n+m+b+1)]
distances = [[INF for _ in range(n+m+b+1)] for _ in range(b+1)]
# 다리 별로 다익스트라를 만들기 위한 distances
for _ in range(k):
    node1, node2, cost = map(int, sys.stdin.readline().rstrip().split())
    nodes[node1].append([node2, cost])
    nodes[node2].append([node1, cost])

def Dijkstra(start):
    pq = []
    heapq.heappush(pq, [0, start])
    distances[start-n-m][start] = 0

    while pq:
        cur_cost, cur_node  = heapq.heappop(pq)

        if distances[start-n-m][cur_node] != cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[start-n-m][next_node] > next_cost + cur_cost:
                distances[start-n-m][next_node] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_node])

for bridge in range(n+m+1, n+m+b+1):
    Dijkstra(bridge)
    # 각 다리에 대해 다익스트라 알고리즘

for _ in range(q):
    s, e = map(int, sys.stdin.readline().rstrip().split())
    answer = INF
    for bridge in range(n+m+1, n+m+b+1):
        answer = min(answer, distances[bridge-n-m][s] + distances[bridge-n-m][e])
        # 특정 다리를 시작점으로 사용했을 때 해당 다리 -> s, 해당 다리 -> e의 합이 s -> e까지 걸리는 거리
    if answer == INF: print(-1)
    else: print(answer)