首页 > 试题广场 >

Sum of Minimum Distatnce

[编程题]Sum of Minimum Distatnce
  • 热度指数:15 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 2048M,其他语言4096M
  • 算法知识视频讲解
Give a undirected graph, each edge’s length is 1, each node has a numeric ID. There are some special nodes in the graph, node’s the minimum distance to the special node is the length of shortest path to the nearest special node. Please calculate all the nodes’ minimum distance to special node. If a node could not reach any special node the distance is –1.

输入描述:
First line is a number N means that the next N lines are the N edges in the graph. Each of the N lines has two value v1 v2 which are the two nodes’ ID linked by this edge. 0 < N < 10000000
After that there is a single line with a number M which means the next M lines are the M special nodes. Each of the M lines has one value v which means the node’s ID. 0 <= M <= N/2


输出描述:
Sum of All nodes' minimum distance
示例1

输入

2
1 2
2 3
1
2

输出

2