Dragon Ball II
Time limit4sMemory limit512 MB
Find the minimum teleport cost from city 1 to collect Dragon Balls with seven pairwise distinct serial numbers, or report -1 if impossible.
- Level
Hard8 of 10
- Topics
- Graph, Shortest path, Dynamic programming, Bit manipulation
- Solved
- No attempts yet
Problem
Long ago, a legend about Dragon Balls was told on Planet X. If you collect seven Dragon Balls, the Dragon God appears and grants your wishes.
That changed when a Dragon Ball radar was discovered. It shows the location of every ball, so collecting all seven became too easy. The Dragon God was tired of being pestered with frivolous wishes, so he made the collection harder. He created a huge number of balls instead of seven. Each ball has a serial number, and several balls may share the same number. To summon the Dragon God, you must collect seven balls whose serial numbers are pairwise distinct. Duplicate serial numbers do not count.
You bought a Dragon Ball radar at a flea market. It tells you the city where each ball is and its serial number. Can you still find the cheapest way to summon the Dragon God?
Planet X has n cities, numbered 1 to n. You start in city 1. To move between cities, you can take any of m bidirectional teleport trips, as many times as you like. The i-th teleporter costs t_i coins each time you use it, and it connects cities a_i and b_i. To collect a ball, you only need to visit its city. Several balls may be in the same city, and visiting that city picks up all of them at once.
Input
The first line contains three integers n, m, and k (1 ≤ n, k ≤ 1 000, 1 ≤ m ≤ 10 000), the number of cities, teleport trips, and Dragon Balls.
The next m lines each contain three integers a_i, b_i, and t_i (1 ≤ a_i, b_i ≤ n, 0 ≤ t_i ≤ 10 000), describing a teleport trip between cities a_i and b_i that costs t_i coins per use.
The next k lines each contain two integers c_i and d_i (1 ≤ c_i, d_i ≤ n). The i-th ball is in city c_i and has serial number d_i. Several balls may share a city, several balls may share a serial number, and a city may hold multiple balls with the same serial number.
Output
Print the minimum number of coins needed to collect seven Dragon Balls with pairwise distinct serial numbers. If the task cannot be completed, print -1.