Informatica Online Judge

  교통체증 [1302 / 0516]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 11


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 최창호)]

Background

경곽이의 나라의 자동차도로는 모든 도로가 일방통행이며 고속도로와 국도 2가지의 도로로 이루어져 있다.

고속도로는 넓기때문에 아무리 많은 차들이 자나도 상수시간이 걸리고 국도는 좁기 때문에 지나가는 차에 비례하는 시간이걸린다.

경곽이의 나라는 국고가 바닥나서 국도가 2개밖에 없다.

경곽이의 나라의 주민인 k명의 사람들은 모두 9시에 집에서 서울로 출근한다.

이 k명의 주민들은 모두가 이기적이기 때문에 자신이 선택했을 때 가장 빠른 시간에 도착할 수 있는 길을 선택한다.
(만약 소모시간이 같은 경로가 여러개있다면 주민들은 국도를 적게 통해서 도착하는 경로를 선호한다.)



예를 들자면 위의 그림과 같은 도로들이 주어졌을 때 10명의 시민들이 지나가야 한다면 9명은 국도 2개와 소모시간이 0인 고속도로를 지나는 경로를 선택하고 1명은 국도와 소모시간이 10인 고속도로를 지나는 경로를 선택한다.

그러므로 총소모시간은 19*9+20=191이다.

Input

먼저 주민의 수 k, 정점의 개수 n과 도로의 개수 m이 입력된다.

그리고 m줄에 걸쳐 도로의 시작 정점, 도착정점 , 고속도로라면 도로의 소모시간 t가 입력된다. 이때 집은 1번째정점이고 서울은 n번째 정점이다.
(국도의 소모시간은 -1로 입력된다.)

[입력값의 정의역]
1 <= k <= 30
2 <= n <= 10
3 <= m <= 200
0 < t <= 120

Output

주민들의 총 소모시간을 출력하여라.

IO Example

입력1
10 4 5
1 2 -1
3 4 -1
1 3 10
2 3 0
2 4 10

출력1
191

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]