python3 bfs

公交车

http://www.nowcoder.com/questionTerminal/630816b6884f4ad49590b6c07bab40fc

import sys
n,m=map(int,input().split())
route=[]
for line in sys.stdin:
    route.append(list(map(int,line.split()))[1:])
def bus(route,n):
    if n==1:
        return 0
    station={}
    for i,routes in enumerate(route):
        for station_id in routes:
            if station_id in station:
                station[station_id].append(i)
            else:
                station[station_id]=[i]
    source_route=station[1]
    target_route=set(station[n])
    res=1
    used_station,used_route=set(),set()
    for route_id in source_route:
        if route_id in target_route:
            return res
        used_route.add(route_id)
    while source_route:
        res+=1
        next_route=[]
        for route_id in source_route:
            for station_id in route[route_id]:
                if station_id not in used_station:
                    for next_route_id in station[station_id]:
                        if next_route_id not in used_route:
                            if next_route_id in target_route:
                                return res
                            next_route.append(next_route_id)
                            used_route.add(next_route_id)
                used_station.add(station_id)
        source_route=next_route
    return -1
print(bus(route,n))

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 00:27
中南大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议