相对论大师-记录型正负性质BFS/图论-链表/数据结构

看到这一题我的第一个思路就是双向bfs

起点是a，终点还是a，但是flag是相反的（“越”的方向）

tip1.可以用字典vis来存储flag

刚开始初始化时vissta,visend一个对应0、1                                        

要求两个队列相接的时候flag要相同

tip2.get_nei函数

读取输入的时候用字典存储了点之间的关系

那么get_nei的时候就需要返回可能的下个节点以及new_flag

new_flag还是在bfs中判断，因为读取输入的时候是用0表示同向，1表示反向

tip3.存储中间过程

由于触碰点是起点和终点中间，所以我们需要记录前驱节点从而进行回溯

那么最适合的就是链表

from collections import deque,defaultdictd=defaultdict(set)n=int(input())for i in range(n):a,n1,b,n2=input().split()if n1==n2:d[a].add((b,0))#明显不能双向：否则会Yu 1 Yuci 0 Yuci 0 Yu 0 = Yu 1 Yu 0#d[b].add((a,0))#双向图?else:d[a].add((b,1))#d[b].add((a,1))def get_nei(cur):neis=d[cur]return neisdef bfs(k):sta=end=kstaq=deque([sta])endq=deque([end])vissta={sta:1}#用0，1表示相对性visend={end:0}presta={sta:None}#记录前驱节点preend={end:None}while staq and endq:ls=len(staq)le=len(endq)if ls<=le:for _ in range(ls):#当前层cur=staq.popleft()flag=vissta[cur]for nei,k in get_nei(cur): #解包if k:nflag= flag #0,1间取反else:nflag=not flagif nei not in vissta:vissta[nei]=nflagstaq.append(nei)presta[nei]=curif nei in visend and visend[nei]==vissta[nei]:return build_path(nei,presta,preend)else:for _ in range(le):cur=endq.popleft()flag=visend[cur]for nei,k in get_nei(cur):if k:nflag=not flag #0,1间取反else:nflag=flagif nei not in visend:visend[nei]=nflagendq.append(nei)preend[nei]=curif nei in vissta and vissta[nei]==visend[nei]:return build_path(nei,presta,preend)return 0def build_path(meet,presta,preend):path_sta=[]cur=meetwhile cur is not None:#开始链表回溯path_sta.append(cur)cur=presta[cur]path_sta.reverse()#掉头，方面后面衔接path_end=[]cur=preend[meet]while cur is not None:path_end.append(cur)cur=preend[cur]return path_sta+path_endprint(d)for i in d:k=bfs(i)print(k)'''不能dfs：不知道何时停止
def dfs()
'''

但是这段代码其实是错的

因为d[x]存的是x后面的节点，是单向的

所以无法从d[x]得到从终点返回的节点，只有d[k]=x遍历字典才能得到k，那还不如单向bfs 

from collections import deque
from collections import defaultdictd = defaultdict(list)n = int(input())
for _ in range(n):a, a_flag, b, b_flag = input().split()a_flag = int(a_flag)b_flag = int(b_flag)d[(a, a_flag)].append((b, b_flag))shortest_path = Nonenodes = set()
for key in d:nodes.add(key[0])for b, _ in d[key]:nodes.add(b)
nodes = list(nodes)for sta in nodes:for start_flag in [0, 1]:target_flag = 1 - start_flagvissta = {}staq = deque()staq.append((sta, start_flag, []))vissta[(sta, start_flag)] = Truefound = Falsewhile staq and not found:cur, flag, path_edges = staq.popleft()if cur == sta and flag == target_flag:if shortest_path is None or len(path_edges) < len(shortest_path):shortest_path = path_edgesfound = Truebreakfor (nei, nei_flag) in d.get((cur, flag), []):if (nei, nei_flag) not in vissta:vissta[(nei, nei_flag)] = Truenew_path = path_edges + \[(cur, flag, nei, nei_flag)]staq.append((nei, nei_flag, new_path))if found and len(shortest_path) == 0:break if shortest_path and len(shortest_path) == 0:break output_steps = []
for step in shortest_path:a, a_flag, b, b_flag = stepoutput_steps.append(f"{a} {a_flag} {b} {b_flag}")sta = shortest_path[0][0]
start_flag = shortest_path[0][1]
end_flag = 1 - start_flagprint(f"{' '.join(output_steps)} = {sta} {start_flag} {sta} {end_flag}")