HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50464 - From Tirana to Durres

Guest
• Review clarifications (1)

Section problems

• 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
• 50691 - The traveling salesman prob...
• 50701 - Cell Removal
• 50703 - The Shortest Path
• 50704 - Connected?
• 50705 - Student Clubs

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 Ibrahim Mesecan.

From Tirana to Durres

Question:
Write a program that finds the shortest path between any two given cities in a directed graph G.

Input specification
The first line contains a number (E) which represents the number of edges Then in the following E lines, it writes the name of two cities (city1 and city2) and an integer number d which means there is a path from the first city (city1) to the second one (city2) with the given distance (d).

At the last line of the input, you will be given the names of two cities (srcCity, destCity). You will find the shortest path from the srcCity to destCity (, if there is any) where 1 ≤ n ≤ 60

Output specification
Show the distance between city1 and city2 if there exists a path. If there is no path show -1.

Sample Input I   
12
Tirana Elbasan 2
Tirana Vlora 4
Tirana Peshkopia 1
Elbasan Peshkopia 3
Elbasan Fier 10
Vlora Durres 5
Peshkopia Vlora 2
Peshkopia Durres 8
Peshkopia Kavaja 4
Fier Peshkopia 2
Fier Kavaja 6
Kavaja Durres 1
Tirana Durres

Sample Output I   
6


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

www.contester.ru