문제

[백준] 임계경로 (Platinum 5)

요약

N(1 <= N < 10,000)개의 도시와 M(1 <= M < 100,000)개의 도로가 주어진다. 모든 도로는 일방통행이고 싸이클이 없다. 시작 도시부터 도착 도시까지 모든 경로를 탐색한다고 할 때, 가장 긴 경로로 갔을 때 걸리는 시간과 가장 긴 경로에 포함된 도로의 개수를 구하여라.

분류

  • 위상 정렬
  • 비트마스킹

풀이

1. 내 풀이 (위상정렬 + 비트마스킹)

Set은 공간 복잡도 때문에 사용하지 못 한다. 결국 비트마스킹을 사용했다. 시간복잡도도 대부분의 경우 O(1)로 효율적이다.

import sys
from collections import deque

input = sys.stdin.readline

n, m = int(input()), int(input())
graph = [[] for _ in range(n)]
indegree = [0] * n
dp_times = [0] * n
dp_cnts = [0] * n

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1].append((b - 1, c, i))
    indegree[b - 1] += 1

start, end = map(int, input().split())
queue = deque([start - 1])

while queue:
    cur_node = queue.popleft()

    for node, time, num in graph[cur_node]:
        indegree[node] -= 1
        if dp_times[node] < dp_times[cur_node] + time:
            dp_times[node] = dp_times[cur_node] + time
            dp_cnts[node] = dp_cnts[cur_node] | (1 << num)
        elif dp_times[node] == dp_times[cur_node] + time:
            dp_cnts[node] |= dp_cnts[cur_node] | (1 << num)
        if indegree[node] == 0:
            queue.append(node)

print(dp_times[end - 1])
print(bin(dp_cnts[end - 1]).count('1'))