|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||95||48||44||55.000%|
As part of his new job at the IT security department of his company, Bob got the task to track how fast messages between the companies’ different offices are transmitted through the internet. Since some offices are currently rebuilt and not finished yet he is not able to simply measure the transmission speed but needs to compute it somehow. Therefore, Bob created a map of all servers that may be involved in routing the packages through the internet. He also gathered the times each server needs to process a message. The total processing time of a message is the sum of the processing times of the sender, all servers along the path, and the receiver. Furthermore, Bob read that messages are sent through the network of servers along a path such that the total processing time of all servers on the path is minimal.
Bob thought that it might be an easy problem to compute the total transmission time between two offices, but he forgot the intelligence agencies! Each server on the internet is controlled by some agency that can decide which packages are routed and which of them are not. All servers are configured in a way that they read all incoming data, since gathering all kind of information is exactly what the intelligence agencies want to do, but not all data is forwarded to other servers.
Each server has a list of pairs of other servers such that messages from the first of them are not sent to the second one. Can you still help Bob to compute how fast his messages will be transmitted?
The input consists of:
Bob’s messages start at server 1 and should go to server n.
Output the sum of the processing times of all servers on the shortest path for Bob’s message including the first and last one, or “impossible” if there is no such path.
4 2 10 0 2 0 3 1 1 1 4 1 2 10 1 2 1 0 4 0 10
3 1 10 0 2 1 10 1 3 1 0 10
Figure K.1: Illustration of the sample inputs.