页面无法加载？点击这里可能会修复。
Placeholder

#8507
子任务

스키장 1s 1024MB

问题

당신은 친구들과 함께 스키를 타러 스키장에 왔다.

스키장에는 일정 고도마다 중간 지점이 설치되어 있다. 중간 지점은 총 N개 있으며,
고도가 감소하는 순서대로 1번부터 N번까지 번호가 매겨져 있다.

즉 가장 높은 지점이 1번 지점, 가장 낮은 지점이 N번 지점이다.

현재 당신은 S번 지점에 친구들과 함께 있다.

당신의 친구들은 각자 자유롭게 스키를 탄 이후, 끝나면 T번 지점에 모이기로 약속했다.

스키장에는 M개의 코스가 있다.

각 코스는 a_i번 지점에서 b_i번 지점 방향으로 이어지며, 코스에 진입하면 t_i분 동안 스키를 탈 수 있다.

코스는 항상 고도가 감소하는 방향으로 이어진다. 즉, a_i < b_i를 만족한다. 

또한, 각 코스에는 스키 리프트가 있다. 스키 리프트는 코스와는 반대 방향으로, 고도가 증가하는 방향으로 이어진다.

즉, 스키 리프트를 타면 b_i번 지점에서 a_i번 지점으로 이동할 수 있다. 스키 리프트는 최대 K번 탑승할 수 있다. 

당신은 스키 코스와 리프트만을 사용해서 T번 지점까지 가되, 스키를 타는 시간을 최대화하려고 한다.

리프트를 타는 시간은 스키를 타는 시간에 포함되지 않는다.

코스의 정보가 주어질 때, 최대 몇 분 동안 스키를 탈 수 있을지 구하여라.


输入

첫 번째 줄에 다섯 개의 정수 N, M, K, S, T (1 \le N, M \le 10^5, 0 \le K \le 10, 1 \le S, T \le N) 가 주어진다. 

이후 M개의 줄에 각 코스의 정보가 세 개의 정수 a_i, b_i, t_i (1 \le a_i < b_i \le N, 1 \le t_i \le 10^9) 로 주어진다. 

서로 다른 두 지점을 잇는 코스는 최대 하나이다.


输出

첫째 줄에 스키를 탈 수 있는 최대 시간을 분 단위로 출력한다.

만약 어떻게 코스와 리프트를 선택해도 T번 지점으로 이동할 수 없다면 -1을 출력한다.


子任务

编号 分数 条件
#114分

M = N - 1, S = 1, T = N

모든 코스에서 a_i = i, b_i = i+1 을 만족한다.

#229分

N \le 1\,000, M = N(N-1)/2

임의의 i, j (i < j)에 대하여 i번 지점에서 j번 지점까지 직접 연결하는 코스가 존재한다.

#335分

K = 0

#422分

추가 제약 조건은 없다.


示例 #1

3 2 1 1 3
1 2 10
2 3 5
25

示例 #2

3 3 1 1 3
1 2 10
2 3 5
1 3 1
30

示例 #3

3 2 1 3 1
1 2 10
2 3 5
-1

示例 #4

3 2 2 3 1
1 2 10
2 3 5
0


来源

UCPC 2021 예선 - H

需要登录才能编写代码。