简答题
偏难
#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 <= qr:
# 将队首的元素出栈,将队首元素称为x
x = q[ql]
ql += 1
# 遍历从x出发能够直接到达的节点
for y in e[x]:
# 如果当前找到的最短路径不如从初始节点到x再多走一步,那么就将y节点入队
if d[x] + 1 < 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] < mx[ans]:
ans = i
print(ans)</pre>
这道题暂未补解析。