백준 5250번 최단 경로들

문제

Nikola는 Bit 마을에 살고 있고 Hex 마을에 사는 Anita의 남자친구이다. Nikola는 주변 지도를 아주 잘 알고 있어서 두 마을 사이의 최단 경로를 찾았다. 그리고 이 경로를 운 좋은 경로라고 부르기로 했다. 주변 지도는 서로 다른 마을을 잇는 양방향 도로의 집합으로 표현된다.

어떤 날, 이 나라의 대통령이 도로에 공사를 하기로 했다. 나라의 교통을 유지하기 위하여, 오직 하루에 하나의 도로만 닫기로 했다.

운 좋은 경로에 있는 도로에 대해서, Nikola는 그 도로가 닫혔을 때 Anita와의 최단 경로의 길이를 알고 싶어 한다.

입력

입력의 첫째 줄은 4개의 정수로 이루어진다: n - 도시의 개수; m - 도로의 개수; a - Bit 마을(Nikola가 살고 있는 마을)의 번호; b - Hex 마을(Anita가 살고 있는 마을)의 번호.

마을들에는 1부터 n까지의 번호가 부여된다. 다음 m개의 줄은 u, v, w 3개의 정수를 포함하며 도로에 대한 정보를 준다: 마을 u와 마을 v는 길이 w의 도로로 이어져 있다.

입력의 마지막 줄은 숫자 k와 k개의 숫자(v1(=a), v2, …, vk(=b))로 이루어 지고, Nikola의 운 좋은 경로를 나타낸다.

출력

각각의 정수 t = 1 … k – 1에 대해, 각 줄마다 도로 (vt, vt+1)가 닫혔을 경우에 마을 a와 마을 b 사이의 최단 경로의 길이를 출력하라. 만약 경로가 없다면 -1을 출력하라.

제한

• 1 ≤ n ≤ 2000, 1 ≤ m ≤ 100.000
• 1 ≤ a, b ≤ n
• 1 ≤ w ≤ 100.000
• 서로 다른 두 도시 사이에는 최대 하나의 도로가 존재한다.
• 주어진 경로는 마을 a와 마을 b 사이의 최단 경로 중 하나이다.

 

2. 코드

 

from heapq import heappush, heappop

INF = 10 ** 9 + 7
size = 1 << 11

class SegTree:
    def __init__(self):
        self.tree = [INF] * (size << 1)
        self.lazy = [INF] * (size << 1)

    def push(self, node):
        if node < size:
            for _next in [node << 1, node << 1 | 1]:
                self.lazy[_next] = min(self.lazy[_next], self.lazy[node])
        self.tree[node] = min(self.tree[node], self.lazy[node])
        self.lazy[node] = INF

    def update(self, l, r, val, node = 1, LEFT = 1, RIGHT = size):
        self.push(node)
        if r < LEFT or RIGHT < l:
            return
        if l <= LEFT and RIGHT <= r:
            self.lazy[node] = min(self.lazy[node], val)
            self.push(node)
            return
        mid = (LEFT + RIGHT) // 2
        self.update(l, r, val, node << 1, LEFT, mid)
        self.update(l, r, val, node << 1 | 1, mid + 1, RIGHT)
        self.tree[node] = min(self.tree[node << 1], self.tree[node << 1 | 1])

    def query(self, l, r, node = 1, LEFT = 1, RIGHT = size):
        self.push(node)
        if r < LEFT or RIGHT < l:
            return INF
        if l <= LEFT and RIGHT <= r:
            return self.tree[node]
        mid = (LEFT + RIGHT) // 2
        return min(self.query(l, r, node << 1, LEFT, mid), self.query(l, r, node << 1 | 1, mid + 1, RIGHT))


def dijkstra(st, graph, dis):
    dis[st] = 0
    queue = [(0, st)]

    while queue:
        dist, now = heappop(queue)
        if dis[now] < dist:
            continue
        for i in graph[now]:
            if dist + i[1] < dis[i[0]]:
                dis[i[0]] = dis[now] + i[1]
                heappush(queue, (dis[i[0]], i[0]))


def DAG(par, dist, now, pre, t):
    stack = [(now, pre, t)]

    while stack:
        now, pre, t = stack.pop()

        if par[now]:
            continue

        if ins[now]:
            t = now

        par[now] = t

        for i in graph[now]:
            if i[0] == pre or dist[now] + i[1] != dist[i[0]]:
                continue

            if not t and ins[i[0]]:
                continue

            stack.append((i[0], now, t))


def solution(n, start, end, graph, path):
    par_start = [0] * 2001
    par_end = [0] * 2001

    dist_start = [INF] * (n + 1)
    dist_end = [INF] * (n + 1)

    dijkstra(start, graph, dist_start)
    dijkstra(end, graph, dist_end)

    DAG(par_start, dist_start, path[0], -1, path[0])
    DAG(par_end, dist_end, path[-1], -1, path[-1])

    ST = SegTree()

    for i in range(1, n + 1):
        for j, cost in graph[i]:
            if ins[i] and ins[j] and abs(ins[i] - ins[j]) <= 1:
                continue
            t1 = ins[par_start[i]]
            t2 = ins[par_end[j]]
            ST.update(t1, t2 - 1, dist_start[i] + cost + dist_end[j])

    ans = []
    for i in range(1, k):
        result = ST.query(i, i)
        ans.append(result if result != INF else -1)

    return ans

n, m, start, end = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

k, *path = list(map(int, input().split()))

ins = [0] * 2001
for index in range(k):
    ins[path[index]] = index + 1

answer = solution(n, start, end, graph, path)

print(*answer, sep="\n")

 

3. 문제 해결법

이 문제는 우선 다익스트라 이긴 한데 너무나 특이 했다.

다익스트라로 돌려 나온 경로들을 가지고 DAG를 형성해서 문제를 풀어 나가는 형식이여서 되게 신박하고 재미있었다.

이렇게 만든 트리를 shortest path tree라 부르는 거 같은데 최단경로 관련 문제에서 성질 찾을 때 종종 쓰인다고 한다.

1. 다익스트라를 돌린다.
2. 최단 경로에 속하는 간선들로 그래프를 다시 만들어보면 항상 DAG가 나온다는 걸 알 수 있다.

이 그래프에서 다시 시작 노드부터 DFS 돌려 스패닝 트리 만들어주면 된다. (하지만 이 문제를 재귀 형태의 DFS이 메모리 초과가 나온다. 이렇게 풀면 신이 와도 못푼다. 그러므로 stack 으로 스패닝트리를 만들면된다.)

​

주의할 점은 스패닝 트리는 항상 문제에서 주어지는 lucky path를 포함하도록 구성해야 한다.
​

​

모든 edge들을 순회하면서 세그 먼트를 업데이트 해주면 된다.

​

​

구간 min 업데이트는 최솟값 세그먼트 트리와 lazy propagation을 이용해 효율적으로 처리할 수 있다.

​