Cheapest fare and how many ways to fly it
A low-cost airline in Southeast Asia sells connecting itineraries. Each flight goes one way from one airport to another with a fixed fare. The revenue team wants to know the cheapest total fare between two airports, and how many different itineraries achieve exactly that cheapest fare (to see how much choice customers have).
Task: the first line holds n and m (2 ≤ n ≤ 40, 0 ≤ m ≤ 200). Each of the next m lines holds from to fare: airport codes (letters and digits, no spaces) and a positive integer fare. No pair (from, to) appears twice. The last line holds the origin and the destination (different airports). An itinerary is a sequence of flights; two itineraries are different if their sequences of airports differ. Print cost count, or UNREACHABLE if there is no itinerary.
Sample test
Input
5 7 DXB LHR 300 DXB CDG 100 CDG LHR 200 DXB IST 150 IST LHR 150 LHR JFK 400 CDG JFK 650 DXB JFK
Expected output
700 3
Your answer is also checked against 5 hidden tests.
Need a hint?
Settle airports in order of cheapest known fare. When you meet an equally cheap way to an airport, add the number of ways instead of replacing it.
Log in or create a free account to run your code, submit and earn points.
Run your code to see the output here. Ctrl + Enter also runs it.