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.
- the start city number
- the destination city number
- 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
|
Для отправки решений необходимо выполнить вход.
|