People's opinions are known to be swayed by the “news”. You have been recently hired by CT (formally called Canada Today). CT wants you to develop a method for spreading fake-news reports effectively amongst important news channels in the U.S. For maximum effect, you have to spread the fake-news reports in the fastest possible way.
The difficulty is that news channels only trust news reports coming from their trusted sources (other news channels whom they trust). So you must take into account the structure of their contacts when spreading a fake-news report. (Assume each contact trusts the source.) It takes a certain amount of time for a specific source news channel to pass the news report on to each of its contact news channels.
Your task is write a program that tells you which news channel to choose as your starting point for the fake-news report, as well as the time it will take for the news report to spread throughout the network. This duration is measured as the time needed for the last news channel to receive the report.
Your program will input data for a number of trials, each for a different set of news channels. Each trial starts with a line with the number of news channels. Following this is a line for each news channel which contains the number of news channels with whom they have contact, who these news channels are, and the time taken for them to pass the message to each. The format of each channel line is then as follows.
The number of contacts (n),
followed by n pairs of integers,
one pair for each contact.
Each pair lists first a number referring to the contact (e.g., ‘1’ means news channel #1 in the set), followed by the time in minutes (a positive integer) taken to pass a news report to that channel.
There are no special punctuation symbols or spacing rules.
Each news channel is numbered 1 through to the number of channels in total. The time taken to pass a news report on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of channels. The number of channels will range from 1 to 100. The input file is terminated by a trial containing 0 (zero) channels.
It is possible that
your program will receive a network of connections
that excludes some news channels;
i.e., some may be unreachable.
If your program detects such a broken network,
simply output the message “disjoint”.
Note that the time taken to pass the message
from channel i to channel j is
not necessarily the same as the time taken
to pass it from j to i,
if such transmission is possible at all.
3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 0 2 2 5 1 5 0
For each trial, your program must output a single line containing the news channel who results in the fastest news report transmission, and how long before the last news channel will receive any given report after you give it to this channel, measured in integer minutes.
3 2 3 10