[BOJ] 1702. 고속도로

문제 링크

가중치가 있는 무방향 그래프가 주어집니다. 각 간선에는 요금과 시간에 해당하는 가중치가 있습니다. 저희의 목표는 주어진 그래프의 모든 최적의 경로들의 서로 다른 비용-시간 쌍의 갯수를 구하는것입니다. 어떤 경로의 비용-시간 쌍이 $(c, t)$일 때, 임의의 경로의 비용-시간 쌍 $(c', t')$에 대하여 $c \leq c'$과 $t \leq t'$을 만족한다면 해당 경로를 최적의 경로라고 부릅니다.

집합 $S = \{(c, t) \, |$ 비용이 $c,$ 시간이 $t$인 최적의 경로가 존재$\}$라고 정의 하겠습니다. 우리가 출력해야 하는 값은 $|S|$가 됩니다.

이 때, 집합 $S$의 모든 원소들은 $c_{1} < c_{2}$이면, $t_{1} > t_{2}$를 만족해야 합니다. 다시말해 $s$에서 $e$로가는 경로들 중에서 각 비용에 대한 최단 경로들의 길이를 구할 수 있다면 그 최단 경로의 길이를 비용이 작은것 부터 큰 순서대로 확인하면서 $|S|$를 구할 수 있습니다.

그럼 각 비용에 대한 최단 경로들의 길이를 어떻게 구할 수 있을까요? 먼저 주어진 그래프를 토대로 아래와 같이 새로운 그래프를 만듭니다.

• 원래 그래프에서 정점 $a$와 $b$를 연결하는 간선 $e$가 존재하고 비용이 $c_{e}$, 시간이 $t_{e}$라면 새로운 그래프에는 정점 $(a, c)$에서 $(b, c+c_{e})$로 향하는 간선과 정점 $(b, c)$에서 $(a, c+c_{e})$로 향하는 간선을 추가합니다. 각 간선은 방향이 있으며 가중치는 $t$입니다.

새롭게 만든 그래프에서 $(s, 0)$에서 $(e, x)$로 가는 최단 경로의 길이는 원래 그래프에서 $s$에서 $e$로 가는 경로들 중에서 비용이 정확히 $x$가 드는 경로들 중 최단 경로의 길이가 됩니다. 즉, 새롭게 만든 그래프에서 다익스트라 알고리즘을 사용하여 각 비용에 대한 최단 경로들의 길이를 구할 수 있습니다.

비용은 최대 $O(n \cdot max(c))$까지만 고려하면 되므로 시간복잡도는 $O(n \cdot m \cdot max(c) (\log{n}+\log{m}+\log{max(c)}))$가 됩니다.