[BOJ 14285] 간선 끊어가기

문제

---

https://www.acmicpc.net/problem/14285

풀이

---

간선 끊어가기 2와 반대되는 문제이다.

비연결이 되는 시점에서, 지운 엣지들의 가중치의 합이 최대이어야 한다.

맨 처음엔,

1. 다익스트라로 최단 거리를 계산한다.

2. 나머지 엣지들을 다 지운다.

3. 최단 경로에서 가중치가 제일 큰 엣지를 지운다.

이런 과정으로 생각했으나,

3 3
1 2 1
2 3 1
1 3 3

같은 반례가 존재했다.

고로 위 과정에서 2, 3번의 순서를 바꿔, 최단 경로를 구하는 과정에서 한 번은 가중치를 무시할 수 있도록 구현해 줘야 한다.

아래 다익스트라 코드에서, 아직 가중치를 무시하지 않은 최단 거리들을 res0에, 한 번 가중치를 무시한 최단 거리들을 res1에 저장했다.

코드

---

import sys
from heapq import heappush, heappop

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
ans = 0
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    ans += c

s, t = map(int, sys.stdin.readline().split())


def dijkstra(graph, start):
    res0 = {node: float('inf') for node in range(1, n + 1)}
    res1 = {node: float('inf') for node in range(1, n + 1)}
    res0[start] = 0
    res1[start] = 0
    queue = [[0, start, 1]]

    while queue:
        old_weight, old_node, flag = heappop(queue)
        if flag:
            if res0[old_node] >= old_weight:
                for new_node, new_weight in graph[old_node]:
                    total_weight = old_weight + new_weight
                    if total_weight < res0[new_node]:
                        res0[new_node] = total_weight
                        heappush(queue, [total_weight, new_node, 1])
                    if old_weight < res1[new_node]:
                        res1[new_node] = old_weight
                        heappush(queue, [old_weight, new_node, 0])
        else:
            if res1[old_node] >= old_weight:
                for new_node, new_weight in graph[old_node]:
                    total_weight = old_weight + new_weight
                    if total_weight < res1[new_node]:
                        res1[new_node] = total_weight
                        heappush(queue, [total_weight, new_node, 0])

    return res1


print(ans - dijkstra(graph, s)[t])