bus-routes

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>routes</code> representing bus routes where <code>routes[i]</code> is a bus route that the <code>ith</code> bus repeats forever.

<ul>
	<li>For example, if <code>routes[0] = [1, 5, 7]</code>, this means that the <code>0th</code> bus travels in the sequence <code>1 -&gt; 5 -&gt; 7 -&gt; 1 -&gt; 5 -&gt; 7 -&gt; 1 -&gt; ...</code> forever.</li>
</ul>

You will start at the bus stop <code>source</code> (You are not on any bus initially), and you want to go to the bus stop <code>target</code>. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from <code>source</code> to <code>target</code>. Return <code>-1</code> if it is not possible.

&nbsp;
Example 1:

<pre>
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
</pre>

Example 2:

<pre>
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
</pre>

&nbsp;

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= routes.length &lt;= 500</code>.</li>
	<li><code>1 &lt;= routes[i].length &lt;= 105</code></li>
	<li>All the values of <code>routes[i]</code> are unique.</li>
	<li><code>sum(routes[i].length) &lt;= 105</code></li>
	<li><code>0 &lt;= routes[i][j] &lt; 106</code></li>
	<li><code>0 &lt;= source, target &lt; 106</code></li>
</ul>

numBusesToDestination

Bus Routes

Minimum Costs Using the Train Line

minimum-costs-using-the-train-line

乘坐火车路线的最少费用

Breadth-First Search

Array

Hash Table

给你一个数组 <code>routes</code> ，表示一系列公交线路，其中每个 <code>routes[i]</code> 表示一条公交线路，第 <code>i</code> 辆公交车将会在上面循环行驶。

<ul>
	<li>例如，路线 <code>routes[0] = [1, 5, 7]</code> 表示第 <code>0</code> 辆公交车会一直按序列 <code>1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...</code> 这样的车站路线行驶。</li>
</ul>

现在从 <code>source</code> 车站出发（初始时不在公交车上），要前往 <code>target</code> 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 <code>-1</code> 。

 

示例 1：

<pre>
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。 
</pre>

示例 2：

<pre>
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
</pre>

 

提示：

<ul>
	<li><code>1 <= routes.length <= 500</code>.</li>
	<li><code>1 <= routes[i].length <= 105</code></li>
	<li><code>routes[i]</code> 中的所有值 互不相同</li>
	<li><code>sum(routes[i].length) <= 105</code></li>
	<li><code>0 <= routes[i][j] < 106</code></li>
	<li><code>0 <= source, target < 106</code></li>
</ul>