늘 삶을 최적화하려는 Bessie는 Farmer John의 $P$개 목초지 중 좋아하는 $F$개 $F_i$를 방문하는 걸 즐깁니다. 번호는 $1,\ldots,P$이며 $1\le F\le P$, $1\le P\le500$, $1\le F_i\le P$입니다.
목초지를 연결하는 $C$개 양방향 길(번호 $1,\ldots,C$, $1\le C\le8,000$)로 모든 목초지에 갈 수 있습니다. 길 $P_i$의 끝은 $a_i,b_i$ ($1\le a_i,b_i\le P$)이고 어느 방향이든 시간 $T_i$ ($1\le T_i\le892$)가 걸립니다.
깨어난 뒤 좋아하는 $F$개 목초지까지 평균 이동 시간이 최소가 되는 잠자리 목초지 번호를 찾고 싶습니다.
아래 예시 지도에서 별표는 좋아하는 목초지, 대괄호 숫자는 길을 지나는 시간입니다.
1*--[4]--2--[2]--3
| |
[3] [4]
| |
4--[3]--5--[1]---6---[6]---7--[7]--8*
| | | |
[3] [2] [1] [3]
| | | |
13* 9--[3]--10*--[1]--11*--[3]--12*다음 표는 후보 4,5,6,7,9,10,11,12에서의 거리입니다.
* * * * * * Favorites * * * * * *
Potential Pasture Pasture Pasture Pasture Pasture Pasture Average
Best Pasture 1 8 10 11 12 13 Distance
------------ -- -- -- -- -- -- -----------
4 7 16 5 6 9 3 46/6 = 7.67
5 10 13 2 3 6 6 40/6 = 6.67
6 11 12 1 2 5 7 38/6 = 6.33
7 16 7 4 3 6 12 48/6 = 8.00
9 12 14 3 4 7 8 48/6 = 8.00
10 12 11 0 1 4 8 36/6 = 6.00 ** BEST
11 13 10 1 0 3 9 36/6 = 6.00
12 16 13 4 3 0 12 48/6 = 8.00이 후보들에 최적의 곳이 있다고 가정하면 (프로그램은 어떤 방법으로든 모든 목초지를 확인해야 합니다) 잠들 최적의 곳은 목초지 10입니다.
입력
- 1줄: 공백으로 나눈 $P,F,C$.
- $2,\ldots,F+1$줄: $i+2$번째 줄에 정수 $F_i$.
- $F+2,\ldots,C+F+1$줄: $i+F+1$번째 줄은 공백으로 나눈 $a_i,b_i,T_i$로 길 $i$를 설명합니다.
출력
- 1줄에 잠자리로 최적인 목초지 번호를 정수로 출력합니다. 여러 곳이면 가장 작은 번호를 고릅니다.
예제
입력 1
13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7출력 1
10참고
문제 설명과 같음
문제 설명과 같습니다.
문제 작성: Rob Kolstad, 2009