BOJ 6048 Water Slides

문제 링크:

문제 내용

마추픽추에 있는 어떤 워터슬라이드는 $V$개의 미니 풀과 이들을 연결하는 $E$개의 단방향 미니 슬라이드로 이루어져 있습니다. 각 미니 풀에는 1번부터 $V$번까지의 번호가 붙어 있습니다. 1번 미니 풀로 입장하면 하나 이상의 미니 슬라이드를 통해서 $V$번 미니 풀에 도착하게 됩니다. 1번을 제외한 모든 미니 풀은 그 풀로 들어오는 미니 슬라이드가 존재하고, $V$번을 제외한 모든 미니 풀은 그 풀에서 나가는 미니 슬라이드가 존재합니다. 또한, 모든 미니 풀에서 유한 개의 미니 슬라이드를 통하여 $V$번 미니 풀에 도달할 수 있고, 사이클은 존재하지 않습니다.

$i$번 미니 슬라이드는 $P_i$번 미니 풀에서 $Q_i$번 미니 풀로 연결되며, 재미의 양을 나타내는 값 $F_i$이 주어집니다. 워터슬라이드를 타면서 얻는 재미는 거쳐간 모든 미니 슬라이드의 재미의 합입니다.

베시는 이 워터슬라이드에서 최대의 재미를 얻고자 각각의 미니 풀에서 다음 미니 슬라이드를 선택할 수 있지만, 내려오는 동안 최대 $K$번은 랜덤한 미니 슬라이드를 타게 됩니다. 가능한 최악의 경우의 재미를 최대화하고자 할 때, 베시가 확실하게 얻을 수 있는 재미의 값을 구하세요.

아래는 워터슬라이드의 예시입니다.

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

$K = 1$이라고 하면, 베시의 선택에 따라 다음과 같은 상황이 될 수 있습니다.

• 1번 풀에서 재미 9짜리 슬라이드를 선택하면, 얻는 최종 재미는 9입니다.
• 1번 풀에서 재미 5짜리 슬라이드를 선택하면, 최선은 5+5=10이지만, 2번 풀에서 랜덤으로 3짜리 슬라이드를 타게 되면 8의 재미만 얻을 수 있습니다.
• 1번 풀에서 랜덤으로 재미 5짜리 슬라이드로 내려왔다면, 2번 풀에서 반드시 5짜리 슬라이드를 고를 수 있습니다.

따라서, 베시가 이 워터슬라이드에서 확실하게 얻을 수 있는 재미는 9입니다.

입력

첫 번째 줄에 $V$, $E$, $K$가 주어집니다. ($2 \le V \le 50\;000$, $1 \le E \le 150\;000$, $1 \le K \le 10$)

다음 $E$줄에 걸쳐서, $i$번째 미니 슬라이드의 시작점 $P_i$, 끝점 $Q_i$, 재미의 값 $F_i$가 한 줄에 주어집니다. ($1 \le P_i, Q_i \le V$, $P_i \neq Q_i$, $0 \le F_i \le 2\;000\;000\;000$)

출력

문제의 정답을 출력합니다.

문제 풀이