HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50698 - Ayran Delivery

Guest
• Review clarifications (7)

Section problems

• 50690 - Parliament
• 50700 - Candidates for the Mayor
• 50692 - How much money?
• 50694 - The Cheapest Flight
• 50841 - My grand-grand-grandfather
• 50697 - Base Stations
• 50695 - Longest link between neurons
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres

Feedback

If you notice incorrect translations in Contester, please let author know.

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


Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.

www.contester.ru