20987번 - Robot 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 218 | 48 | 41 | 21.244% |
문제
There are N crossings in the IOI town, numbered from 1 to N. There are M roads, numbered from 1 to M. Each road connects two different crossings in both directions. The road i (1 ≤ i ≤ M) connects the crossing Ai and the crossing Bi. No two different roads connect the same pair of crossings. Each of the roads has a color, which is described as an integer between 1 and M, inclusive. Currently, the color of the road i is Ci. More than one road may have the same color.
The JOI Co., Ltd. developed a robot moving around the crossings of the IOI town. Whenever you tell a color to the robot, the robot will find the road with that color, and then the robot will pass through it and moves to the adjacent crossing. However, if there are more than one roads with the told color connected to the current crossing of the robot, it cannot decide which road it should pass through, and will halt.
The robot is currently in the crossing 1. Your task is to move the robot to the crossing N by telling colors to it. However, it is not always true that the robot can be moved to the crossing N. You may change the colors of some of the roads in advance so that the robot can be moved to the crossing N. It costs Pi yen to change the color of the road i (1 ≤ i ≤ M) to any color between 1 and M, inclusive.
Write a program which, given the information of the crossings and the roads, calculates the minimum total cost. However, if it is impossible to move the robot to the crossing N even if you change the colors of the roads, output -1 instead.
입력
Read the following data from the standard input. Given values are all integers.
N M A1 B1 C1 P1 . . . AM BM CM PM
출력
Write one line to the standard output. The output should contain the minimum total cost. However, if it is impossible to move the robot to the crossing N even if you change the colors of the roads, output -1 instead.
제한
- 2 ≤ N ≤ 100 000.
- 1 ≤ M ≤ 200 000.
- 1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M).
- (Ai, Bi) ≠ (Aj, Bj) (1 ≤ i < j ≤ M).
- 1 ≤ Ci ≤ M (1 ≤ i ≤ M).
- 1 ≤ Pi ≤ 1 000 000 000 (1 ≤ i ≤ M).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 34 | N ≤ 1 000, M ≤ 2 000. |
| 2 | 24 | Pi = 1 (1 ≤ i ≤ M). |
| 3 | 42 | No additional constraints. |
예제 입력 1
4 6 1 4 4 4 3 4 1 3 1 3 4 4 2 4 3 1 2 3 3 2 1 2 4 2
예제 출력 1
3
You can change the color of the road 4 from color 3 to color 4 at the cost of 1 yen. You can change the color of the road 6 from color 4 to color 2 at the cost of 2 yen. The total cost is 3 yen.
After that, you tell the color 2 to the robot, then it moves from the crossing 1 to the crossing 2. And, you tell the color 4 to the robot, then it moves to the crossing 4.
It is impossible to pay less than 3 yen so that the robot can be moved to the crossing 4. Hence output 3.
예제 입력 2
5 2 1 4 1 2 3 5 1 4
예제 출력 2
-1
It is impossible to move the robot to the crossing 5 even if you change the colors of the roads. Hence output -1.
예제 입력 3
5 7 2 3 7 1 1 4 5 1 4 5 3 1 3 4 7 1 2 4 3 1 3 5 6 1 1 2 5 1
예제 출력 3
1
예제 입력 4
13 21 7 10 4 4 3 6 4 7 8 10 4 5 3 9 2 5 1 4 4 5 2 6 4 2 3 11 2 2 3 8 16 2 8 11 16 1 6 10 4 14 6 8 16 6 9 12 16 5 5 13 4 6 1 12 4 7 2 4 4 18 2 9 4 10 2 12 4 6 10 13 4 28 5 7 2 5 5 11 2 16 7 13 4 20
예제 출력 4
7
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호