시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
0.3 초 512 MB 5052 1375 (27%) 1153
문제
$N$ 개 농장의 (편의상 $1 ,2, \cdots , N$) 의 대표 암소 한 마리가, $X ( 1 \le X \le N)$ 농장에서 열리는 파티에 참석하려고 한다. 농장들은 단방향의 길들로 연결되어 있으며, 각 길마다 걸어가는데 걸리는 시간이 주어진다. 모든 소들은 파티에 걸어가야 하고 파티가 마친 후에는 자기가 속한 농장으로 돌아와야 한다. 모든 소들은 게을러서 가장 최단시간으로 올수 있는 최적의 길을 선택하려고 한다. 모든 소 들 중에서 농장으로 갔다가 돌아오는 데 가장 많이 걸리는 소의 시간은 얼마인가?
입력
* 첫 번째 줄 : 정수 $N , M , X$ 가 주어진다. $(1 \le N \le 1,000)$는 농장의 수, $(1 \le M \le N \times (N-1))$은 도로의 갯수, $(1 \le X \le N)$는 파티가 열리는 농장이다. * 두 번재 줄에서 $M+1$ 번째 줄 : $i+1$ 번째 줄은 세 정수 $A_{i},B_{i},T_{i}$ 가 주어진다. $A_{i}$ 에서 $B_{i}$ 로 가는데 $T_{i}$ 시간이 소요된다는 것이다. $(T_{i} < 10,000)$
출력
파티에 참석했다 돌아오는 소 들 중 가장 긴 시간을 출력한다.
힌트
### 입력 예제 ### ``` 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 ``` ### 출력 예제 ### ``` 10 ``` 4 -> 2 ( 3 ) 2 -> 1 -> 3 -> 4 (7) 총 거리합은 10이고, 이 때가 가장 긴 경우이다. ![alt text](/download_file/2fa57883e91d6906f30f78942f3377ce7a45a05f97a8702d40951e40b5131f8b/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202017-02-15%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%202.35.26.png/?show=true)