Dragon Ball I
Time limit2sMemory limit512 MB
Given a weighted undirected graph and seven target cities, find the minimum total cost of a walk starting at city 1 that visits all seven targets.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Bit manipulation, Dynamic programming
- Solved
- No attempts yet
Statement
On Planet X there is a legendary tale about Dragon Balls: if you collect seven Dragon Balls, the Dragon God will appear and grant you a wish.
One day you learn that the tale might be true. You found a Dragon Ball radar at a flea market. The radar shows the locations of the seven Dragon Balls on Planet X. You want to waste no time and check for yourself whether the old legend about wish-granting holds.
Planet X has n cities, numbered from 1 to n. You are currently in city 1. To travel between cities you can use any of m bidirectional teleporters, as many times as you like. Using the i-th teleporter once costs ti coins, and it moves you between cities ai and bi. To pick up a Dragon Ball, you only need to visit the city where it is located, as shown on your radar. Several Dragon Balls may be in the same city; if you visit that city, you pick all of them up at once.
Input
The first line contains two space-separated integers n and m, the number of cities and the number of teleporters. (1 ≤ n, m ≤ 200 000)
The next m lines each contain three space-separated integers ai, bi, and ti. (1 ≤ ai, bi ≤ n, 0 ≤ ti ≤ 10 000) As explained above, these are the two cities connected by the teleporter and the cost of using it.
Then follows one line of seven space-separated integers, the city IDs of the seven Dragon Balls shown on the radar. Each ID c satisfies 1 ≤ c ≤ n.
Output
Print the minimum number of coins you need to spend to collect all seven Dragon Balls shown on the Dragon Ball radar. If this is impossible, print -1 instead.