second-minimum-time-to-reach-destination

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A city is represented as a bi-directional connected graph with <code>n</code> vertices where each vertex is labeled from <code>1</code> to <code>n</code> (inclusive). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [ui, vi]</code> denotes a bi-directional edge between vertex <code>ui</code> and vertex <code>vi</code>. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is <code>time</code> minutes.

Each vertex has a traffic signal which changes its color from green to red and vice versa every&nbsp;<code>change</code> minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.

The second minimum value is defined as the smallest value strictly larger than the minimum value.

<ul>
	<li>For example the second minimum value of <code>[2, 3, 4]</code> is <code>3</code>, and the second minimum value of <code>[2, 2, 4]</code> is <code>4</code>.</li>
</ul>

Given <code>n</code>, <code>edges</code>, <code>time</code>, and <code>change</code>, return the second minimum time it will take to go from vertex <code>1</code> to vertex <code>n</code>.

Notes:

<ul>
	<li>You can go through any vertex any number of times, including <code>1</code> and <code>n</code>.</li>
	<li>You can assume that when the journey starts, all signals have just turned green.</li>
</ul>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/e1.png" style="width: 200px; height: 250px;" /> &emsp; &emsp; &emsp; &emsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/e2.png" style="width: 200px; height: 250px;" />
<pre>
Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
Output: 13
Explanation:
The figure on the left shows the given graph.
The blue path in the figure on the right is the minimum time path.
The time taken is:
- Start at 1, time elapsed=0
- 1 -&gt; 4: 3 minutes, time elapsed=3
- 4 -&gt; 5: 3 minutes, time elapsed=6
Hence the minimum time needed is 6 minutes.

The red path shows the path to get the second minimum time.
- Start at 1, time elapsed=0
- 1 -&gt; 3: 3 minutes, time elapsed=3
- 3 -&gt; 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -&gt; 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes. 
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/eg2.png" style="width: 225px; height: 50px;" />
<pre>
Input: n = 2, edges = [[1,2]], time = 3, change = 2
Output: 11
Explanation:
The minimum time path is 1 -&gt; 2 with time = 3 minutes.
The second minimum time path is 1 -&gt; 2 -&gt; 1 -&gt; 2 with time = 11 minutes.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 104</code></li>
	<li><code>n - 1 &lt;= edges.length &lt;= min(2 * 104, n * (n - 1) / 2)</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ui, vi &lt;= n</code></li>
	<li><code>ui != vi</code></li>
	<li>There are no duplicate edges.</li>
	<li>Each vertex can be reached directly or indirectly from every other vertex.</li>
	<li><code>1 &lt;= time, change &lt;= 103</code></li>
</ul>

secondMinimum

Second Minimum Time to Reach Destination

Network Delay Time

network-delay-time

网络延迟时间

Find the City With the Smallest Number of Neighbors at a Threshold Distance

find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance

阈值距离内邻居最少的城市

Number of Ways to Arrive at Destination

number-of-ways-to-arrive-at-destination

到达目的地的方案数

Breadth-First Search

Graph

Shortest Path

城市用一个 双向连通 图表示，图中有 <code>n</code> 个节点，从 <code>1</code> 到 <code>n</code> 编号（包含 <code>1</code> 和 <code>n</code>）。图中的边用一个二维整数数组 <code>edges</code> 表示，其中每个 <code>edges[i] = [ui, vi]</code>&nbsp;表示一条节点&nbsp;<code>ui</code> 和节点&nbsp;<code>vi</code> 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 <code>time</code>&nbsp;分钟。

每个节点都有一个交通信号灯，每 <code>change</code> 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都&nbsp;同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点&nbsp;信号灯是绿色时 才能离开。如果信号灯是&nbsp; 绿色 ，你 不能 在节点等待，必须离开。

第二小的值 是&nbsp;严格大于 最小值的所有值中最小的值。

<ul>
	<li>例如，<code>[2, 3, 4]</code> 中第二小的值是 <code>3</code> ，而 <code>[2, 2, 4]</code> 中第二小的值是 <code>4</code> 。</li>
</ul>

给你 <code>n</code>、<code>edges</code>、<code>time</code> 和 <code>change</code> ，返回从节点 <code>1</code> 到节点 <code>n</code> 需要的 第二短时间 。

注意：

<ul>
	<li>你可以 任意次 穿过任意顶点，包括 <code>1</code> 和 <code>n</code> 。</li>
	<li>你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。</li>
</ul>

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/e1.png" style="width: 200px; height: 250px;" />        <img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/e2.png" style="width: 200px; height: 250px;" />

<pre>
输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
输出：13
解释：
上面的左图展现了给出的城市交通图。
右图中的蓝色路径是最短时间路径。
花费的时间是：
- 从节点 1 开始，总花费时间=0
- 1 -&gt; 4：3 分钟，总花费时间=3
- 4 -&gt; 5：3 分钟，总花费时间=6
因此需要的最小时间是 6 分钟。

右图中的红色路径是第二短时间路径。
- 从节点 1 开始，总花费时间=0
- 1 -&gt; 3：3 分钟，总花费时间=3
- 3 -&gt; 4：3 分钟，总花费时间=6
- 在节点 4 等待 4 分钟，总花费时间=10
- 4 -&gt; 5：3 分钟，总花费时间=13
因此第二短时间是 13 分钟。 
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/eg2.png" style="width: 225px; height: 50px;" />

<pre>
输入：n = 2, edges = [[1,2]], time = 3, change = 2
输出：11
解释：
最短时间路径是 1 -&gt; 2 ，总花费时间 = 3 分钟
第二短时间路径是 1 -&gt; 2 -&gt; 1 -&gt; 2 ，总花费时间 = 11 分钟</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= n &lt;= 104</code></li>
	<li><code>n - 1 &lt;= edges.length &lt;= min(2 * 104, n * (n - 1) / 2)</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ui, vi &lt;= n</code></li>
	<li><code>ui != vi</code></li>
	<li>不含重复边</li>
	<li>每个节点都可以从其他节点直接或者间接到达</li>
	<li><code>1 &lt;= time, change &lt;= 103</code></li>
</ul>