Problem D
Vacation Time
Tyko is a massive aviation enthusiast (aren’t we all?) with one dream: to fly on the legendary Airbus A380 — the largest commercial aircraft ever built. As the undisputed king of the skies, the A380 holds a special place in Tyko’s heart, just as Tyko rules the world of kindergarten.
Unfortunately, not everyone shares his love for the superjumbo jet. With declining popularity and the final A380 already manufactured, time is running out for Tyko’s dream to take flight.
But there’s hope! Tyko’s family is planning a trip to the ICPC World Finals this year, and they’ll be flying to get there. This could be Tyko’s golden opportunity to experience the A380 before it disappears from the skies for good.
There’s just one catch — Måns wants to keep the travel costs as low as possible. Tyko has, however, scraped the internet after all available flights and their cost. So he has a list of all flights that they possibly could take and what airline flies that route. He hasn’t been able to find the cheapest route. Can you help Tyko find the cheapest possible flight itinerary that still includes a ride on the iconic A380.
Input
The first line of input contains 2 integers $A, F$ ($3 \leq A \leq 10000$ and $2 \leq F \leq 100000$), the number of airports and the number of flights.
Then follow $F$ lines with 3 integers and one string: $O_i, D_i, C_i, M_i$ where $0 \leq O_i < A$ is the origin of flight $i$, $0 \leq D_i < A$ is the destination, $1 \leq C_i \leq 10^5$ is the cost and $M_i$ is a string with the airplane model.
The trip starts at airport number $0$, and the ICPC world finals will be held at airport number $A - 1$.
Output
Output a line containing a single integer: the minimal cost when taking the A380 as part of the trip. If it is not possible to find such a trip, then output $-1$
Scoring
|
Group |
Points |
Constraints |
|
$1$ |
$10$ |
$C = 1$, Only one A380 trip avalible |
|
$2$ |
$20$ |
Only one A380 trip avalible |
|
$3$ |
$70$ |
No additional constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 5 0 3 1 A380 0 1 1 B777 0 3 1 E170 1 2 1 CRJ700 2 3 1 Q400 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 0 1 100 A380 0 2 100 B737 |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 8 0 1 700 A350 0 2 1000 CRJ900 1 2 500 A330 2 3 500 B737 3 1 500 MD-80 3 4 800 A380 4 2 750 B757 5 0 250 E190 |
-1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
6 8 0 1 700 A350 0 2 1000 CRJ900 1 2 500 A330 2 3 500 B737 3 1 500 MD-80 3 4 800 A380 4 5 750 B757 5 0 250 E190 |
3050 |
