ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > CEN303_2016Questions > задача:


HW112. 50698 - Ayran Delivery

CEN303_2016Questions

Старт: 28.окт.2016 в 17:00:00
Финиш: 01.ноя.2016 в 05:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (7)

Задачи турнира

• HW072. 51043 - Genome Sequencing
• HW081. 51044 - Number of Trees
• HW082. 50699 - Fighting Vampires
• HW083. 50671 - Phalanx
• HW091. 51061 - The Longest Path
• HW101. 50682 - Hotel Durres
• HW102. 51067 - Jumping frog
• HW111. 50506 - The Biggest Island
• HW112. 50698 - Ayran Delivery
• PE11. 51023 - Preparing Keyword I...
• PE12. 50835 - Club Presidency
• PE13. 51024 - Total Stock Price
• PE14. 50998 - CEN112 Homework, ...
• PE21. 51071 - Phalanx-2
• PE22. 51072 - Castle on chessboard
• RE1. 51079 - Key person - 2
• RE2. 51080 - Deepest Point

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
IMPC 2014-15 Ind_04-50.

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