Khanty-Mansiysk to Paris
Time limit2sMemory limit512 MB
Given phone numbers grouped by five time zones, find a chain from Polikarp to the professor through adjacent zones minimizing the sum of message costs, where cost depends on the longest matching digit prefix.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Dynamic programming, Trie
- Solved
- No attempts yet
Problem
In 2050, the leadership of the Global Telephone Network (GTN) decided on a new pricing system for short text messages. Now the price of sending one message depends on how many leading digits of the sender's and recipient's phone numbers match. If the first c digits of the phones match and the (c + 1)-th digit differs, the message costs (10 - c) credits (0 ≤ c ≤ 9). All phone numbers are ten digits long. The GTN also allows each subscriber to send a message only within their own time zone or time zones that differ from it by 1 hour.
A schoolboy, Polikarp, from Khanty-Mansiysk (time +2 hours from Moscow) successfully solved all the problems of the first round of the school olympiad in informatics. Now he wants to tell his teacher, Professor de Coder, in Paris (time -2 hours from Moscow) about it. Since Khanty-Mansiysk and Paris are not in neighboring time zones, Polikarp cannot send a message directly. So he makes use of his friends who live in Khanty-Mansiysk, Paris, and the intermediate time zones: Dubai (time +1 hour from Moscow), Moscow, and Kaliningrad (time -1 hour from Moscow). Polikarp's friends will relay this important information to Professor de Coder along a chain. Polikarp wants to organize the transmission so that the total cost of sending all messages is minimized.
Write a program that determines the delivery chain for which the total cost of the sent messages is minimal.
Input
The first two lines of the input file contain the phone numbers of Polikarp and Professor de Coder. Then follow 5 data blocks describing Polikarp's friends living in Khanty-Mansiysk, Dubai, Moscow, Kaliningrad, and Paris, respectively. Each block starts with a line containing a single number ni (1 ≤ ni ≤ 100 000), the number of Polikarp's friends in the corresponding city, followed by ni lines with the friends' phone numbers. All phone numbers consist of exactly 10 digits. The sum of all ni does not exceed 100 000. All phone numbers in the input are distinct.
Output
In the first line of the output file, print the minimum possible cost w of transmitting the information and the number k of phone numbers involved in the chain. Then print k phone numbers describing the chain itself, in order from Polikarp to Professor de Coder. The first number in the chain must match Polikarp's phone number, and the last must match Professor de Coder's phone number. If there are several solutions, print any of them.