Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Osman Ay.
Ayran Delivery
Question:
Ramadan is the time when restaurants make a lot of
money in Ankara and there are already N restaurants
(numbered from 1 to N) with given number of daily
visitors. You know how to make the best Ayran in
the world. It is so good that all restaurants want
to hire you and even if you won’t choose them they
are ready to buy Ayran from the restaurant you are
working in.
You don’t care about money at all and the only important
thing for you is to deliver Ayran to as many people
as possible. But the problem is that Ayran loses its
original taste if it is delivered to places further
than M meters from you.
If there are E direct roads between restaurants select
one of them, so that the number of people who could
taste your original Ayran is maximum.
Input specification
On the first line there three integers N, M, E
(1 ≤ N ≤ 500, M ≤ 10,000, E < 150,000).
On the second line there are N integers
v_i – number of visitors in restaurant i (vi ≤ 1,000).
Each of next E lines contains three integers fi, ti, li,
where fi and ti – numbers of restaurants connected,
li – the length of the road in meters
(1 ≤ fi, ti ≤ 500, 0 < li ≤ 10,000).
Output specification
The number of the restaurant you have chosen. If there are
more than one restaurants giving the same result,
print the restaurant with the smallest number.
Sample Input I
5 5 4
2 2 2 2 2
1 5 3
5 3 3
2 5 3
4 5 3
|
Sample Input II
5 3 2
0 2 2 2 2
2 3 2
4 5 2
|
Sample Output I
5
|
Sample Output II
2
|
Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.
|