shortest-distance-after-road-addition-queries-ii

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 integer <code>n</code> and a 2D integer array <code>queries</code>.

There are <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code>. Initially, there is a unidirectional road from city <code>i</code> to city <code>i + 1</code> for all <code>0 &lt;= i &lt; n - 1</code>.

<code>queries[i] = [ui, vi]</code> represents the addition of a new unidirectional road from city <code>ui</code> to city <code>vi</code>. After each query, you need to find the length of the shortest path from city <code>0</code> to city <code>n - 1</code>.

There are no two queries such that <code>queries[i][0] &lt; queries[j][0] &lt; queries[i][1] &lt; queries[j][1]</code>.

Return an array <code>answer</code> where for each <code>i</code> in the range <code>[0, queries.length - 1]</code>, <code>answer[i]</code> is the length of the shortest path from city <code>0</code> to city <code>n - 1</code> after processing the first <code>i + 1</code> queries.

&nbsp;
Example 1:

<div class="example-block">
Input: n = 5, queries = [[2,4],[0,2],[0,4]]

Output: [3,2,1]

Explanation: 

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image8.jpg" style="width: 350px; height: 60px;" />

After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image9.jpg" style="width: 350px; height: 60px;" />

After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image10.jpg" style="width: 350px; height: 96px;" />

After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
</div>

Example 2:

<div class="example-block">
Input: n = 4, queries = [[0,3],[0,2]]

Output: [1,1]

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image11.jpg" style="width: 300px; height: 70px;" />

After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image12.jpg" style="width: 300px; height: 70px;" />

After the addition of the road from 0 to 2, the length of the shortest path remains 1.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= queries[i][0] &lt; queries[i][1] &lt; n</code></li>
	<li><code>1 &lt; queries[i][1] - queries[i][0]</code></li>
	<li>There are no repeated roads among the queries.</li>
	<li>There are no two queries such that <code>i != j</code> and <code>queries[i][0] &lt; queries[j][0] &lt; queries[i][1] &lt; queries[j][1]</code>.</li>
</ul>

shortestDistanceAfterQueries

Shortest Distance After Road Addition Queries II

Greedy

Graph

Array

Ordered Set

给你一个整数 <code>n</code> 和一个二维整数数组 <code>queries</code>。

有 <code>n</code> 个城市，编号从 <code>0</code> 到 <code>n - 1</code>。初始时，每个城市 <code>i</code> 都有一条单向道路通往城市 <code>i + 1</code>（ <code>0 &lt;= i &lt; n - 1</code>）。

<code>queries[i] = [ui, vi]</code> 表示新建一条从城市 <code>ui</code> 到城市 <code>vi</code> 的单向道路。每次查询后，你需要找到从城市 <code>0</code> 到城市 <code>n - 1</code> 的最短路径的长度。

所有查询中不会存在两个查询都满足 <code>queries[i][0] &lt; queries[j][0] &lt; queries[i][1] &lt; queries[j][1]</code>。

返回一个数组 <code>answer</code>，对于范围 <code>[0, queries.length - 1]</code> 中的每个 <code>i</code>，<code>answer[i]</code> 是处理完前 <code>i + 1</code> 个查询后，从城市 <code>0</code> 到城市 <code>n - 1</code> 的最短路径的长度。

&nbsp;

示例 1：

<div class="example-block">
输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]

输出： [3, 2, 1]

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image8.jpg" style="width: 350px; height: 60px;" />

新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image9.jpg" style="width: 350px; height: 60px;" />

新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image10.jpg" style="width: 350px; height: 96px;" />

新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。
</div>

示例 2：

<div class="example-block">
输入： n = 4, queries = [[0, 3], [0, 2]]

输出： [1, 1]

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image11.jpg" style="width: 300px; height: 70px;" />

新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image12.jpg" style="width: 300px; height: 70px;" />

新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。
</div>

&nbsp;

提示:

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= queries[i][0] &lt; queries[i][1] &lt; n</code></li>
	<li><code>1 &lt; queries[i][1] - queries[i][0]</code></li>
	<li>查询中不存在重复的道路。</li>
	<li>不存在两个查询都满足 <code>i != j</code> 且 <code>queries[i][0] &lt; queries[j][0] &lt; queries[i][1] &lt; queries[j][1]</code>。</li>
</ul>