CTF-2019年4月西湖杯-Misc

Misc

0x1 最短路径

资深宅“flag{”在朋友邀请下，参加了一场聚会。

在聚会上看到了美女“75D}”,一时心花荡漾、不能自己，坚信彼此就是天造地设的一双。

想通过层层朋友的关系认识她，却无奈性格问题，不敢劳师动众。

好在朋友帮忙搞到一张聚会人员关系图，如下：

[('FloraPrice','E11'),('FloraPrice','E9'),('FloraPrice','75D}'),('NoraFayette','E11'),('NoraFayette','E10'),('NoraFayette','E13'),('NoraFayette','E12'),('NoraFayette','E14'),('NoraFayette','E9'),('NoraFayette','E7'),('NoraFayette','E6'),('E10','SylviaAvondale'),('E10','MyraLiddel'),('E10','HelenLloyd'),('E10','KatherinaRogers'),('VerneSanderson','E7'),('VerneSanderson','E12'),('VerneSanderson','E9'),('VerneSanderson','E8'),('E12','HelenLloyd'),('E12','KatherinaRogers'),('E12','SylviaAvondale'),('E12','MyraLiddel'),('E14','SylviaAvondale'),('E14','75D}'),('E14','KatherinaRogers'),('FrancesAnderson','E5'),('FrancesAnderson','E6'),('FrancesAnderson','E8'),('FrancesAnderson','E3'),('DorothyMurchison','E9'),('DorothyMurchison','E8'),('EvelynJefferson','E9'),('EvelynJefferson','E8'),('EvelynJefferson','E5'),('EvelynJefferson','E4'),('EvelynJefferson','E6'),('EvelynJefferson','E1'),('EvelynJefferson','E3'),('EvelynJefferson','E2'),('RuthDeSand','E5'),('RuthDeSand','E7'),('RuthDeSand','E9'),('RuthDeSand','E8'),('HelenLloyd','E11'),('HelenLloyd','E7'),('HelenLloyd','E8'),('OliviaCarleton','E11'),('OliviaCarleton','E9'),('EleanorNye','E5'),('EleanorNye','E7'),('EleanorNye','E6'),('EleanorNye','E8'),('E9','TheresaAnderson'),('E9','PearlOglethorpe'),('E9','KatherinaRogers'),('E9','SylviaAvondale'),('E9','MyraLiddel'),('E8','TheresaAnderson'),('E8','PearlOglethorpe'),('E8','KatherinaRogers'),('E8','SylviaAvondale'),('E8','BrendaRogers'),('E8','LauraMandeville'),('E8','MyraLiddel'),('E5','TheresaAnderson'),('E5','BrendaRogers'),('E5','LauraMandeville'),('E5','CharlotteMcDowd'),('E4','CharlotteMcDowd'),('E4','TheresaAnderson'),('E4','BrendaRogers'),('E7','TheresaAnderson'),('E7','SylviaAvondale'),('E7','BrendaRogers'),('E7','LauraMandeville'),('E7','CharlotteMcDowd'),('E6','TheresaAnderson'),('E6','PearlOglethorpe'),('E6','BrendaRogers'),('E6','LauraMandeville'),('E1','LauraMandeville'),('E1','BrendaRogers'),('E3','TheresaAnderson'),('E3','BrendaRogers'),('E3','LauraMandeville'),('E3','CharlotteMcDowd'),('E3','flag{'),('E2','LauraMandeville'),('E2','TheresaAnderson'),('KatherinaRogers','E13'),('E13','SylviaAvondale')]

你能在让最少人知道的情况下，帮助flag先生联系上75D小姐姐吗？

求节点“flag{”到“75D”的最短路径，即为flag，比如：flag{E3AliceBobXXXXXXXXXXXXXXXX75D}

我是采用BFS算法，由于我输入的数据还不完整，所以可能会存在flag错误

import heapq
import math
graph = {
"FloraPrice":{'E11','E9','75D}'},
"NoraFayette":{'E11','E10','E13','E12','E14','E9','E7','E6'},
"E10":{'SylviaAvondale','MyraLiddel','HelenLloyd','KatherinaRogers'},
"VerneSanderson":{'E7','E12','E9','E8'},
"E12":{'HelenLloyd','KatherinaRogers','SylviaAvondale','MyraLiddel'},
"E14":{'SylviaAvondale','75D}','KatherinaRogers'},
"FrancesAnderson":{'E5','E6','E8','E3'},
"DorothyMurchison":{'E9','E8'},
"EvelynJefferson":{'E9','E8','E5','E4','E6','E1','E3','E2'},
"RuthDeSand":{'E5','E7','E9','E8'},
"HelenLloyd":{'E11','E7','E8'},
"OliviaCarleton":{'E11','E9'},
"EleanorNye":{'E5','E7','E6','E8'},
"E9":{'TheresaAnderson','PearlOglethorpe','KatherinaRogers','SylviaAvondale','MyraLiddel',"EvelynJefferson","FloraPrice"},
"E8":{'TheresaAnderson','PearlOglethorpe','KatherinaRogers','SylviaAvondale','BrendaRogers','LauraMandeville','MyraLiddel',"HelenLloyd","EvelynJefferson"},
"E5":{'TheresaAnderson','BrendaRogers','LauraMandeville','CharlotteMcDowd',"EvelynJefferson","EvelynJefferson"},
"E4":{'CharlotteMcDowd','TheresaAnderson','BrendaRogers',"EvelynJefferson"},
"E7":{'TheresaAnderson','SylviaAvondale','BrendaRogers','LauraMandeville','CharlotteMcDowd',"RuthDeSand","HelenLloyd"},
"E6":{'TheresaAnderson','PearlOglethorpe','BrendaRogers','LauraMandeville',"EvelynJefferson"},
"E1":{'LauraMandeville','BrendaRogers',"EvelynJefferson"},
"E3":{'TheresaAnderson','BrendaRogers','LauraMandeville','CharlotteMcDowd','flag{',"EvelynJefferson"},
"flag{":{"E3"},
"TheresaAnderson":{"E3","E8","E9","E5","E7","E6","E3"},
"BrendaRogers":{"E6","E3","E7","E5","E1","E3","E8"},
"CharlotteMcDowd":{"E5","E3","E7","E4"},
"LauraMandeville":{"E1","E3","E7","E8"},
"SylviaAvondale":{"E7","E9","E8","E12","E10","E14"},
"MyraLiddel":{"E9","E12","E10"},
"PearlOglethorpe":{"E9","E8"},
"75D}":{"E14","FloraPrice"},
"E2":{'LauraMandeville','TheresaAnderson',"EvelynJefferson"},
"E11":{"HelenLloyd","FloraPrice"},
"KatherinaRogers":{'E13',"E14","E10"},
"E13":{'SylviaAvondale',"OliviaCarleton","NoraFayette"}
}
def BFS(graph,s):
	queue = []
	queue.append(s)
	seen = set()
	seen.add(s)
	parent = {s: None}
	while(len(queue)>0):
		vertex = queue.pop(0)
		nodes = graph[vertex]
		for w in nodes:
			if w not in seen:
				queue.append(w)
				seen.add(w)
				parent[w] = vertex
	return parent
parent = BFS(graph,"flag{")
v='75D}'	
while v!=None:
	print(v)
	v=parent[v]