运行要求运行时限：2sec内存限制：1024MB未经允许，原链接不允许转载房间和M路。房间编号为1到N，道路编号为1到M。道路i连接房间Ai和Bi，使Ai和Bi可以双向行驶。任意两个房间之间都有或多或少的道路。1号房间是洞窟的出口，是一个特殊的房间。除了房间1以外的房间，洞穴非常暗。为每个房间设置路标。这个路标指向通往这个房间的道路另一端的房间。因为洞穴危险，除了1号房以外的房间，需要满足以下条件。从这个房间开始，【根据当前房间唯一的路标，前往路标所指的房间】，重复这个操作，直到知道是否可以用到房间1的最近路线到达目标，如果可能的话，输出一个排列路标方案。输入先决条件所有输入都是整数2<=N<=10^51<=M<=2*10^51<=Ai,Bi<=N(1<=i<=M)Ai!=Bi(1<=i<=M)任意两个房间之间有通道，将它们连接在一起输入和输入遵循以下形式标准输入NMA1B1A2B2...AMBM输出如果满足条件的方案不存在，则输出“否”"如果存在则输出N行。第1行输出“Yes”，i(2<=i<=N)，输出第i个房间的路标所指向的另一个房间的编号示例1输入4412233442输出Yes122Go如输出所示Arrange路标从2号房间开始，从2->1移动1次，这是最小的，从3号房间开始，移动3->2->1，移动2次，这是最小的，从4号房间开始，移动4->2->1，移动2第二，这是最小的。因此，输出中显示的路标布局方案是最优方案。例子2输入69346124534615624556输出是65511答案有很多，随便输出都能看懂题目简单点吧。例2画出解题思路的输入输出。让我们简单谈谈想法。标题说每两个房间之间会有通道，所以所有房间都可以通过通道连接到1号房间。如果房间i的深度是Li，那么房间j的路标应该指向距离最近的深度为Li-1的房间。使用bfs遍历代码N,M=map(int,input().split())ARR=[]foriinrange(M):ARR.append(list(map(int,input().split())))fromcollectionsimportdequedefprepare(n,m,arr):nodes=[[]foriinrange(n)]nodeStates=[-1foriinrange(n)]prevs=[-1foriinrange(n)]foriinrange(m):startNode=arr[i][0]-1endNode=arr[i][1]-1nodes[startNode].append(endNode)nodes[endNode].append(startNode)返回节点，nodeStates，prevsnodes，nodeStates，prevs=prepare(N,M,ARR)defbfs(nodes,nodeStates,prevs,n):q=deque()q.append({'prev':-1,'to':0})whilelen(q)>0:first=q.popleft()currentNode=first['to']previousNode=first['prev']ifnodeStates[currentNode]!=-1:continueprevs[currentNode]=previousNodechildNodes=nodes[currentNode]nodeStates[currentNode]=1forchildNodeinchildNodes:q.append({'prev':currentNode,'to':childNode})print("Yes")foriinrange(1,n):print(prevs[i]+1)bfs(nodes,nodeStates,prevs,N)总结一下这道题，考察一下对bfs的理解※ 另外发在微信个人部分文章在订阅号推出，欢迎关注
