简答题 偏难
#16945

城市规划

城市规划

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false"># tokens里面缓存了输入 tokens = [] # 这个函数将输入的内容放到tokens里面,随后再读取tokens里的第一条内容作为输入 def get_val():     while not tokens:         tokens.extend(input().split())     return int(tokens.pop(0)) # 得到城市和边的数量 n = get_val() m = get_val() # 邻接表,每一个节点后面的列表表示这个节点到列表里面的节点有边 e = [[] for _ in range(n + 1)] for _ in range(m):     u = get_val()     v = get_val()     e[u].append(v)     e[v].append(u) # 假设当前在遍历节点i,则d[j]表示节点i目前发现的到j的最短距离。如果这个值为n+1则表明我们还没遍历到j,否则表示我们已经遍历到了j d = [0] * (n + 1) # 这个列表其实是队列,用在以i为中心的广度优先搜索中,记录即将被bfs遍历到的节点 q = [0] * (n + 2) # 这个数组缓存了各个城市的建设成本 mx = [0] * (n + 1) def bfs(u):     # 初始化d数组,表明所有节点都还没被遍历到     for i in range(1, n + 1):         d[i] = n + 1     # 初始节点已经被遍历到了     d[u] = 0     # 将初始节点入队     q[1] = u     # 广度优先的队列左右边界,初始化为1,表明还没开始遍历。这个队列的长度是n+2,而一共只有n个节点,所以这个队列肯定不会被装满,一个节点只会入队不超过1次     ql, qr = 1, 1     # 只要队列还不空就继续遍历     while ql &lt;= qr:         # 将队首的元素出栈,将队首元素称为x         x = q[ql]         ql += 1         # 遍历从x出发能够直接到达的节点         for y in e[x]:             # 如果当前找到的最短路径不如从初始节点到x再多走一步,那么就将y节点入队             if d[x] + 1 &lt; d[y]:                 d[y] = d[x] + 1                 # 理论上来讲,使用数组一样的数据结构存储队列元素,这里需要取模。但是这道题里面,每一个节点只会入队一次,所以qr最大就到n+1,因此不需要取模                 qr += 1                 q[qr] = y     # 队列中最后一个弹出的元素一定是最后入队的,这个元素一定离初始节点最远,所以他的距离就是建设难度     mx[u] = d[q[qr]] ans = 1 for i in range(1, n + 1):     bfs(i)     # 判断当前的建设难度是否小于之前找到的最小的,如果是则更新答案     if mx[i] &lt; mx[ans]:         ans = i print(ans)</pre>
这道题暂未补解析。