개발자 크루

[RecurDyn]

취미로 코딩하는 RecurDyn 개발자 모임

Lv.4

썸네일

[한양대 HCPC 2023] Pay2Win

난이도
4 단계
참가자
0 명
제출
0 명
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 1초 1024MB
JavaScript 5초 1024MB
C 1초 1024MB
Java 3초 1024MB
Python 5초 1024MB

하이비는 최근 새로운 게임을 만들었다. 이 게임은 현찰을 사용해야 하는, 일명 Pay2Win 게임이다.


게임 개발의 마무리에 들어가는 하이비는 이제 보스전만을 남겨놓았으며, 보스전의 패턴까지는 미리 계획을 해놓았다. 하이비가 계획한 보스전의 패턴은 다음과 같다.


- 보스 스테이지는 N개의 구역으로 나뉘어 있으며, 플레이어는 하이비가 선택한 시작 위치에서 시작한다.

- 보스는 K개의 패턴을 사용하며, 각 패턴의 번호는 K 이하의 서로 다른 양의 정수이다.

- 보스는 모든 패턴을 번호순으로 하나씩 사용한다. 각각의 패턴은 (i, j, x)로 표현할 수 있으며, 이는 i번 위치와 j번 위치를 바꾸는 패턴이다. 즉, 플레이어가 i번 위치에 있었다면 j번 위치로, j번 위치에 있었다면 i번 위치로 이동한다. 플레이어는 이 패턴을 x원을 지불해 건너뛸 수 있다.

- 보스의 체력은 H로 시작하며, 보스의 체력이 0이 되면 플레이어의 승리로 게임이 끝난다.

- K개의 패턴이 모두 지난 뒤, 플레이어가 N번 구역에 있으면 플레이어가 보스의 체력을 1 깎으며, 그렇지 않은 경우 플레이어의 패배로 게임이 끝난다.

- 게임이 끝나지 않은 경우, K개의 패턴을 다시 차례로 거친 뒤 플레이어가 N번 구역에 있는지 확인하는 작업을 반복한다. 이때 플레이어가 시작 위치로 돌아가지는 않지만, 이미 건너뛴 패턴을 다시 건너뛰려면 비용을 다시 지불해야 한다.


하이비는 최대한 많은 수익을 내고 싶기 때문에, 플레이어가 승리하기 위해 지불해야 하는 최소 비용을 최대화하는 시작 위치를 선정하기로 했다. 단, 공정한 게임을 위해, 시작 위치에서 승리할 수 있는 방법이 있어야 한다.

제약조건

1 ≤ N ≤ 200,000

0 ≤ K ≤ 200,000

1 ≤ H ≤ 100

0 ≤ x ≤ 109

입력형식

첫 번째 줄에 구역의 개수 N과 패턴의 개수 K, 보스의 체력 H가 공백으로 구분되어 주어진다.

두 번째 줄부터 K개의 줄에 걸쳐, p+1번째 줄에는 보스의 p번 패턴을 의미하는 3개의 정수 i, j, x가 공백으로 구분되어 주어진다.

출력형식

첫 번째 줄에 하이비가 시작 지점을 적절히 선정했을 때 플레이어가 지불해야 하는 최소 비용을 출력한다.

입력예제1

3 5 2
1 3 10
1 3 20
1 2 30
1 2 40
1 3 50
출력예제1

40
입력예제2

4 2 1
1 2 1000000000
3 4 0
출력예제2

0