Informatica Online Judge

  R&E가는길2 (Large) [0480 / 01E0]

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


The Champion of this Problem (C++) : gs15108 - 0ms / 1619byte
My Best Submission (C++) : N/A

[koistudy.net (28th 최성우)]

Background

앞서 두 문제와 마찬가지로 여전히 R&E를 간다. 하지만 이번에는 무조건 걸어가야 된다. 하지만 a군데의 위치에 탈 것(걷는것 보다 빠름)이 존재한다. 이것으로 갈 수 있는 방법이 완전히 달라진다.





단, 모든 사항은 아래 조건을 만족한다.

- 모든 값은 정수이다.
- 모든 간선은 양방향 이동 가능한 간선이다.
- 걸을 때의 속도는 1로 한다.
- 탈 것의 속도는 1보다 빠르고 50보다는 같거나 느리다.
- 두 지점간의 가중치는 1,000미만의 자연수이다.
- 탈 것으로 이동하는 시간은 간선의 "가중치/탈것의 속도"이다.
- 방문한 지점에 탈 것이 있더라도 타거나 안타거나 선택할 수 있다.
- 항상 1번 지점에서 출발한다.
- 중간에 탈 것을 갈아탈 수 있다.

이러한 사항을 고려하여 s대학교로 R&E를 가는데 최단 시간을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 정점의 수 n과 간선의 수 e, 그리고 s대학교의 정점번호와 탈 것의 수 a가 공백으로 구분되어 입력된다.

다음 줄 부터 e줄에 걸쳐서 출발정점과 도착정점 그리고 가중치가 공백으로 구분되어 입력된다.

다음 줄 부터 a줄에 걸쳐서 탈 것의 속도위치하는 정점이 공백으로 구분되어 입력된다.
(단, 정점 a에서 b로가는 간선이 여러 개 있을 수 있으며, 자기 자신으로 가는 간선도 있을 수 있다.)

[입력값의 정의역]
2 <= n <= 50
1 <= e <= 150
0 <= a < n

[Sub-Task Info]
#1 : n<=20, e<=30
#2 : 추가제한조건은 없다.

Output

구한 최소값을 소수점 3째자리까지 나타낸다. (단, 4째자리에서 반올림한 값을 나타낸다. 즉 %.3lf를 이용하면 된다.)

IO Example

입력1
2 1 2 0
1 2 1

출력1
1.000

입력2
7 8 7 3
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
3 5 20
2 7 40
2 3
3 4
4 5

출력2
33.333

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