首页 > 试题广场 >

公交车

[编程题]公交车

热度指数：2119 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一座城市有 n 个公交站台，站点从 1 到 n 编号，和 m 班公交车，公交车从 1 到 m 编号，乘坐每班公交车只需花费 1 元钱，第 i 班公交车一共经过 t_i 个站点，分别为站点 a_i,1，a_i,2，...，a_i,ti，小明可以乘坐第 i 班公交车从这 t_i个站台中的任意一个到达任意一个站点，如一班公交车经过站点 1，2，3，那么小明花费 1 元钱就可以从 1 到 2 ，从 1 到 3 ，从 2 到 1，从 3 到 1，从3 到 2。

小明想从 1 号站台到 n 号站台，问他最少花费多少钱。

数据范围： $2 \le n \le 10^5\$ ， $1 \le m \le 10^5 \$ ， $2 \le t_i \le n \$ ， $2 \le n_i \times \sum_{i=1}^{m} t_i \le 10^5 \$

输入描述:

第一行两个数 n , m。
接下来 m 行，依次描述公交车经过的站点，第 i 行开头一个数 t_i ，表示第 i 班公交车经过的站点数，接下来的 t_i 个数，依次表示这 t_i 个站点。

输出描述:

输出一个数，从 1 号站点到 n 号站点的最小代价，如果不能达到则输出 -1。

示例1

输入

输出

说明

先坐第一班公交车从 1 号到 3 号站点，再坐第三班公交车从 3 号站点到 5 号站点。

算法知识视频讲解

Python

嫑葱3Q

n,m = list(map(int,input().split()))
edges = []
for _ in range(m):
    t = list(map(int,input().split()))
    for i in range(1,t[0]):
        for j in range(i+1,t[0]+1):
            edges.append([t[i],t[j]])
adjacent = {}
for index in range(1,n+1):
    adjacent[index] = []
for i in range(len(edges)):
    if edges[i][1] not in adjacent[edges[i][0]]:
        adjacent[edges[i][0]].append(edges[i][1])
    if edges[i][0] not in adjacent[edges[i][1]]:
        adjacent[edges[i][1]].append(edges[i][0])

def bfs(route,cost):
    flag = True
    if route[-1] == 5:
        project.append(cost)
        flag = False
    if flag:
        for next_station in adjacent[route[-1]]:
            if next_station not in route:
                bfs(route+[next_station],cost+1)

project = []
route = [1]
cost = 0
bfs(route,cost)
print(min(project))

10%，哭了

发表于 2019-09-07 13:36:01 回复(0)