HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50694 - The Cheapest Flight

Guest
• Review clarifications (1)

Section problems

• 50255 - Bishops
• 50261 - Roads
• 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

Feedback

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

Time limit 2000/4000/4000/4000 ms. Memory limit 1500/25000/65000/65000 Kb.
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