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

Турниры > APGC-1 > задача:


6. 50694 - The Cheapest Flight

APGC-1

Старт: 04.фев.2017 в 18:00:00
Финиш: 05.фев.2017 в 14:00:00
Турнир завершён!
• Турнирная таблица

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

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

• 1. 51069 - Last Digit of a Fibonacci ...
• 2. 50458 - Weekly Report
• 3. 50742 - King Arthur II
• 4. 50930 - Tom and Jerry
• 5. 51073 - Campus Tours for High S...
• 6. 50694 - The Cheapest Flight

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 1500/25000/65000/65000 Кб.
Prepared by Ibrahim Mesecan.

The Cheapest Flight

International Air Transport Association (IATA) is preparing a website where you can search for the cheapest ticket price. There are different prices from city to city. And also, the prices change according to the direction. So, the price to return may be different.

There are thoudands of cities. And with the current program, they are having memory and program runtime difficulties. Now, they decided to improve the program. And thus, they can handle searches for the cheapest ticket price among 2000 differnet cities.

Question: Write a program that is going to read the ticket prices for different flights, and then your program will show the the cheapest ticket price for given two cities.

Input specification
You will be first given two integers: the number of cities (n) and the number of flights (nf) where 2 ≤ (n and nf) ≤ 2000. The cities are conveniently numbered from 1 to n. Then, in the following nf lines you will be given three integers.

  1. the start city number
  2. the destination city number
  3. the cost: an integer less than 2000
Then in the last line, you will be given two integers: the start and the destination cities for which you will search for the cheapest ticket price.

Output specification
If there is path from the start city to destination city, show the cost of the cheapest flight. Print -1 (minus one), if there is no possible flight.

Sample Input I Sample Input II
4 3
2 3 150
3 4 125
1 2 100
1 4
4 2
2 1 200
3 4 50
1 4
Sample Output I Sample Output II
375
-1


Для отправки решений необходимо выполнить вход.

www.contester.ru