5077 : 차이 최적화 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 개의 변수 $x_i$ 와 $M$ 개의 제약 $x_{v_i} - x_{u_i} \le c_i$ 가 주어집니다. $x_1=0$ 으로 고정할 때, $x_N$ 이 가질 수 있는 최댓값을 구하십시오.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le M \le 500000$
• $1 \le A_i < B_i \le N$
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le M \le 500000$
• $1 \le A_i < B_i \le N$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$ 이 주어집니다.
출력 설명
최댓값을 출력하십시오. 도달할 수 없는 경우 -1을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
1 2 5
2 3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
이 문제는 1번 정점에서 N번 정점까지의 최단 경로 문제와 동일합니다.