Informatica Online Judge

  친구집 방문 [1683 / 0693]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 85   Total Tried : 87


The Champion of this Problem (C++) : gs15105 - ms / 545byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

N개의 마을에 각각 한 명의 학생이 살고 있다. 이 N명의 학생이 S (1 ≤ S ≤ N) 마을에 살고있는 친구집을 방문하고자 한다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 최단시간으로 친구집이 있는 S 마을을 방문하고 싶다. N명의 학생들 중 가는데 가장 많은 시간을 소비하는 학생의 소요시간을 알고자 한다.

Input

첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 10,000), S가 공백으로 구분되어 입력된다. 두 번째 줄부터 마을의 시작과 끝, 도로를 지나는데 필요한 소요시간 Ti 이 순서대로 입력되어 있다.

Output

N명의 학생들 중 최단시간으로 S마을에 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

IO Example

입력
6 20 3
3 2 45
6 1 66
6 2 31
2 4 94
5 3 46
5 2 79
3 1 64
4 3 74
3 5 59
1 6 93
3 6 45
6 4 40
3 4 67
1 3 61
1 2 42
4 2 50
4 1 55
2 6 93
5 4 95
1 4 54

출력
168

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