美文网首页
misc-最短的路

misc-最短的路

作者: Watanuki | 来源:发表于2019-10-10 18:00 被阅读0次

题目

资深宅“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}

分析

翻译一下就是拿到了所有连线情况,要得到A-B的最短路径。我们把连线转换为字典,一共34个人。
因为不带权重,直接套用邻接表的遍历算法就行。

payload

# 图的有向无value邻接链表表示法
c = [('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')]
Relation = {}
for i in c:
    Relation.setdefault(i[0],[])
    Relation.setdefault(i[1], [])
    Relation[i[0]].append(i[1])
    Relation[i[1]].append(i[0])

Beauty = '75D}'
Beast = 'flag{'
graph = Relation

# 从图中找出从起始顶点到终止顶点的所有路径
import copy

def find_path_all(curr, end, path):
    '''
    :param curr: 当前顶点
    :param end: 要到达的顶点
    :param path: 当前顶点的一条父路径
    :return:
    '''
    if curr == end:
        path_tmp = copy.deepcopy(path)
        path_all.append(path_tmp)
        return
    if not graph.get(curr):
        return
    for v in graph[curr]:
        if (v in path) or (len(path)>5): #防止死循环,限定最长路径
            continue
        # 构造下次递归的父路径
        path.append(v)
        find_path_all(v, end, path)
        path.pop()


path_all = []
find_path_all(curr=Beast, end=Beauty, path=[Beast])
print ([''.join(x) for x in path_all])

把最短路径值从低到高,试到5的时候跑出来有两种flag:
flag{E3EvelynJeffersonE9FloraPrice75D}
flag{E3TheresaAndersonE9FloraPrice75D}

总结

算法还是要好好学啊,留个作业,带权重的最短路径。

相关文章

  • misc-最短的路

    题目 分析 翻译一下就是拿到了所有连线情况,要得到A-B的最短路径。我们把连线转换为字典,一共34个人。因为不带权...

  • DDCTF部分wp

    MISC-签到题 flag见公告 MISC-(╯°□°)╯︵ ┻━┻ ……被群里的思路带歪了想了好久反转和aaen...

  • 最短的路

    若干年前,英国《泰晤士报》曾出了一个谜题,公开征求答案,题目是:“从伦敦到罗马,最短的道路是什么?” 很多人拿着地...

  • 那条最短的路

    是不是存在一条最短的路,可以让生活工作顺利。摆脱失控与无力。 我观察自己,看似随意的背后,有写对失败结果的恐慌。 ...

  • 最短的路与最快的路

    一个乘客上了一辆出租车,并说出了自己想要到达的目的地。 司机问:“先生,你是要走最短的路,还是最快的路?” 乘客很...

  • 改变世界最短的路

    你是真的愿意让自己的世界变得更美好吗?你是真的渴望让自己的世界变得更丰盛吗?你是真的相信你值得拥有更幸福的...

  • 最短的路未必最快

    这天,一职员正在急急忙忙赶着上班。因为这天公司有个很重要的会议,会议中的表现关乎到能否升职,所以不能迟到...

  • 改变对方最短的路?

    幸福的婚姻千篇一律,不幸福的婚姻各有各的不幸。 我朋友他们两口子从来就没有吵过架,因为老公是宠妻狂魔,爱老婆胜过爱...

  • 最短的路,未必是最快的路

    4月18日 星期日 阴 每周一早上9点,都是固定的周例会,而且雷打不动的不允许迟到,不允许请假。但今天出了...

  • 用最简单的方式直抵羊群

    2019年11月16日 理想可以让你花最短的时间,消耗最少的精力,走最长的路。 狼总是走最短的路来达到目的,可以...

网友评论

      本文标题:misc-最短的路

      本文链接:https://www.haomeiwen.com/subject/hslcuctx.html