|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||3||2||2||66.667%|
ISPs live on very thin margins, so saving money in selecting the optimum route for network traffic is important for the survival of the company. Your job is to find the cheapest route between two hosts on the Internet for the person sending the data. Network traffic that passes over the provider's own network is essentially free and therefore costs \$0 to send traffic through. Network traffic that passes over other people's networks costs \$1 per node traversed.
Input will consist of a series of networks for you to examine. Each network will consist of a number indicating the number of network links that then follow. Each network link is presented as a pair of names representing a unidirectional connection from the first name to the second name. These are then followed by a number representing how many of those nodes are owned by the person sending the packet. This is then followed by a number representing how many pairs of nodes to find a route between. This is followed by a pair of nodes, source first then destination. A network of 0 nodes will terminate the input and should not be processed. A network will have no more than 100 nodes.
Output will consist of a number representing the cost of sending that packet. Nodes that are owned by the sender cost zero, nodes that aren't owned cost 1. The source and destination nodes count towards the cost.
5 Alice Bob Bob Charlie Alice Charlie Charlie Dave Dave Alice 2 Alice Bob 2 Alice Bob Bob Alice 0