转跳到内容

【红包inside!】萌新的算法挑战#2~


推荐贴

Ciallo~我又来建设和谐美好学习论坛辣~看到了 @big_yellow_doge 发布的一个算法帖子,一时手痒~也来发一个~

说起算法,我想到了一个好玩的树问题:

引用

话说在SS大学啊,有一群可爱的小伙伴们~他们每个人都有着一个独特的UID,并且每个人都有着无数的帖子,并且每个帖子都有着很多人回复~

你是一个受到了Kris惩罚的人,Kris麻麻惩罚你从茫茫人海之中最快速的找到她(速通!),这样她就会十分的开心~与此同时为了增加难度,你无法看到帖子的任意版面,想让你的眼中只有她的Kris让你只能通过一个人的Profile去访问这个人的帖子~

那么,你要如何才能满足Kris麻麻的需求,拿到整个SS大学所有同仁的UID呢?

在这个问题之中,输入如下所示~

引用

第一行:N:int 为整个论坛的总人数

第二行:UID:string 初始UID - 是Kris麻麻给你的起点!

第三行:target:string 是Kris麻麻的UID!(ps: 是142805哦~)

从第四行开始,是N个UID和所有回复这个UID的人~

例如:

141950: 是这个人的UID!

308342, 269320, ...: 是回复这个人的所有UID!

输出则是一个找到Kris麻麻最快的线路~

引用

[141950, 142805] 毕竟Kris直接回复了我!

假设你可以从任意UID中必定找到一条路径找出Kris麻麻,那么,你会如何速通找到Kris麻麻呢?

Sample Code:

引用
# 你也可以重写这里~
def main():
    N = int(input())
    UID = input()
    target = input()
    address_map = {}
    for i in range(0, N):
        tmp_uid = input()
        tmp_reply = input().split(',')
        address_map[tmp_uid] = tmp_reply
    # Implement your code there~

 

回复即可获得

剩 388节操


还剩 21 份
注释
骚男 骚男 30.00节操 递糖,(κris来的好快!)
链接到点评
  • 4 周后...

(看了看,BFS裸题吗)

那么就根据题意输入建立邻接表,广搜就可以啦

再优化点可以把反向邻接表建出来,跑双端BFS。

不过麻烦但是并不困难的内容就是根据最短距离来写出路径了(visit哈希表标记下路径转移即可)

 

(虽然说是树的问题,事实上一个人的UID会在多个地方出现吧,并不能简单由下至上推出来,还是变成了有向有环图)

,由Muriya Tensei修改

Muriya Tensei 获得了红包 7.44节操

链接到点评

看了好一会儿才理解是什么意思(大概吧):kl:

5 小时前,Muriya Tensei说道:

(看了看,BFS裸题吗)

那么就根据题意输入建立邻接表,广搜就可以啦

再优化点可以把反向邻接表建出来,跑双端BFS。

不过麻烦但是并不困难的内容就是根据最短距离来写出路径了(visit哈希表标记下路径转移即可)

 

(虽然说是树的问题,事实上一个人的UID会在多个地方出现吧,并不能简单由下至上推出来,还是变成了有向有环图)

感觉说的很对,BFS就行了,虽然确实是有环图,但是并不影响就是了。极端一点甚至能把每条边的权重都设为1,然后用Floyd算法来找最短路径。:SS05:

顺便一提,如果数据非常非常大(爆掉内存),甚至还能直接DFS。。。

yyh 获得了红包 21.48节操

yyh看指路牌的时候拾起一片古怪的叶子,被河童用4节操买來高兴地吃掉了

链接到点评
  • 2 周后...
  • 4 周后...
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款