首页 > 试题广场 >

公交车

[编程题]公交车

热度指数：2103 时间限制：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 号站点。

算法知识视频讲解

牛客486456043号

发表于 2024-08-19 11:12:34

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static List<List 展开全文

秦时明月2022

发表于 2022-08-18 17:07:24

解题思路 1.同条路线的站点互通只需要一辆公交车即可,建立虚拟节点连接同条公交路线的各个站点,以此建图;每条公交路线的虚拟节点不一样,且不能与实际节点重合,虚拟节点编号可考虑在一个基础值之上递增;从source到target的路径数除以2即为最小代价; 代码 #include <bits/st 展开全文

bandiaoz

发表于 2024-12-29 00:13:17

解题思路这是一道使用BFS求解最短路径的问题，主要思路如下：问题分析：个公交站点，条公交线路每条线路经过若干站点每次乘坐花费1元求从1号站到号站的最少花费解决方案：构建双向图：站点和公交线路都作为节点站点与经过它的公交线路之间建立边使用BFS寻找最短路径最终结展开全文

sunnyu

发表于 2021-03-19 17:29:47

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== 展开全文

17c89

发表于 2024-01-06 12:18:54

import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { private static HashS 展开全文