Pro.ID21731 TitleTRAFFIC ENGINEERING Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21731 AC0 Submit0 Ratio- 时间&空间限制描述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. 输出Description 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 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 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. Sample Input 5
Alice Bob
Bob Charlie
Alice Charlie
Charlie Dave
Dave Alice
2
Alice
Bob
2
Alice Bob
Bob Alice
0 Sample Output 0
2 Source 样例输入5
Alice Bob
Bob Charlie
Alice Charlie
Charlie Dave
Dave Alice
2
Alice
Bob
2
Alice Bob
Bob Alice
0 样例输出0
2 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 18:01 , Processed in 0.018257 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
