新增道路查询后的最短距离 I

100379. 新增道路查询后的最短距离 I

给你一个整数 n 和一个二维整数数组 queries。

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

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

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

示例 1：

输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]

输出： [3, 2, 1]

解释：

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

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

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

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]

输出： [1, 1]

解释：

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

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

提示：

3 <= n <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
查询中没有重复的道路。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) { } };

golang 解法, 执行用时: 29 ms, 内存消耗: 7.1 MB, 提交时间: 2024-08-10 12:15:27

func shortestDistanceAfterQueries(n int, queries [][]int) []int {
	from := make([][]int, n)
	f := make([]int, n)
	for i := 1; i < n; i++ {
		f[i] = i
	}

	ans := make([]int, len(queries))
	for qi, q := range queries {
		l, r := q[0], q[1]
		from[r] = append(from[r], l)
		if f[l]+1 < f[r] {
			f[r] = f[l] + 1
			for i := r + 1; i < n; i++ {
				f[i] = min(f[i], f[i-1]+1)
				for _, j := range from[i] {
					f[i] = min(f[i], f[j]+1)
				}
			}
		}
		ans[qi] = f[n-1]
	}
	return ans
}

// bfs
func shortestDistanceAfterQueries2(n int, queries [][]int) []int {
	g := make([][]int, n-1)
	for i := range g {
		g[i] = append(g[i], i+1)
	}

	vis := make([]int, n-1)
	bfs := func(i int) int {
		q := []int{0}
		for step := 1; ; step++ {
			tmp := q
			q = nil
			for _, x := range tmp {
				for _, y := range g[x] {
					if y == n-1 {
						return step
					}
					if vis[y] != i {
						vis[y] = i
						q = append(q, y)
					}
				}
			}
		}
	}

	ans := make([]int, len(queries))
	for i, q := range queries {
		g[q[0]] = append(g[q[0]], q[1])
		ans[i] = bfs(i + 1)
	}
	return ans
}

python3 解法, 执行用时: 281 ms, 内存消耗: 16.8 MB, 提交时间: 2024-08-10 12:14:51

class Solution:
    # bfs
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        g = [[i + 1] for i in range(n - 1)]
        vis = [-1] * (n - 1)

        def bfs(i: int) -> int:
            q = deque([0])
            for step in count(1):
                tmp = q
                q = []
                for x in tmp:
                    for y in g[x]:
                        if y == n - 1:
                            return step
                        if vis[y] != i:
                            vis[y] = i
                            q.append(y)
            return -1

        ans = [0] * len(queries)
        for i, (l, r) in enumerate(queries):
            g[l].append(r)
            ans[i] = bfs(i)
        return ans

    # dp
    def shortestDistanceAfterQueries2(self, n: int, queries: List[List[int]]) -> List[int]:
        frm = [[] for _ in range(n)]
        f = list(range(n))
        ans = []
        for l, r in queries:
            frm[r].append(l)
            if f[l] + 1 < f[r]:
                f[r] = f[l] + 1
                for i in range(r + 1, n):
                    f[i] = min(f[i], f[i - 1] + 1, min((f[j] for j in frm[i]), default=inf) + 1)
            ans.append(f[-1])
        return ans

java 解法, 执行用时: 13 ms, 内存消耗: 44.6 MB, 提交时间: 2024-08-10 12:14:15

class Solution {
    // dp
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<Integer>[] from = new ArrayList[n];
        Arrays.setAll(from, i -> new ArrayList<>());
        int[] f = new int[n];
        for (int i = 1; i < n; i++) {
            f[i] = i;
        }

        int[] ans = new int[queries.length];
        for (int qi = 0; qi < queries.length; qi++) {
            int l = queries[qi][0];
            int r = queries[qi][1];
            from[r].add(l);
            if (f[l] + 1 < f[r]) {
                f[r] = f[l] + 1;
                for (int i = r + 1; i < n; i++) {
                    f[i] = Math.min(f[i], f[i - 1] + 1);
                    for (int j : from[i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
            ans[qi] = f[n - 1];
        }
        return ans;
    }

    // bfs
    public int[] shortestDistanceAfterQueries2(int n, int[][] queries) {
        List<Integer>[] g = new ArrayList[n - 1];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            g[i].add(i + 1);
        }

        int[] ans = new int[queries.length];
        int[] vis = new int[n - 1];
        for (int i = 0; i < queries.length; i++) {
            g[queries[i][0]].add(queries[i][1]);
            ans[i] = bfs(i + 1, g, vis, n);
        }
        return ans;
    }

    private int bfs(int i, List<Integer>[] g, int[] vis, int n) {
        List<Integer> q = new ArrayList<>();
        q.add(0);
        for (int step = 1; ; step++) {
            List<Integer> tmp = q;
            q = new ArrayList<>();
            for (int x : tmp) {
                for (int y : g[x]) {
                    if (y == n - 1) {
                        return step;
                    }
                    if (vis[y] != i) {
                        vis[y] = i;
                        q.add(y);
                    }
                }
            }
        }
    }
}

cpp 解法, 执行用时: 312 ms, 内存消耗: 115.7 MB, 提交时间: 2024-08-10 12:13:31

class Solution {
public:
    // bfs，每次加边后重新跑一遍 BFS，求出从 0 到 n−1 的最短路。
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> g(n - 1);
        for (int i = 0; i < n - 1; i++) {
            g[i].push_back(i + 1);
        }
        vector<int> vis(n - 1, -1);

        auto bfs = [&](int i) -> int {
            vector<int> q = {0};
            for (int step = 1; ; step++) {
                vector<int> nxt;
                for (int x : q) {
                    for (int y : g[x]) {
                        if (y == n - 1) {
                            return step;
                        }
                        if (vis[y] != i) {
                            vis[y] = i;
                            nxt.push_back(y);
                        }
                    }
                }
                q = move(nxt);
            }
        };

        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            g[queries[i][0]].push_back(queries[i][1]);
            ans[i] = bfs(i);
        }
        return ans;
    }

    // dp
    vector<int> shortestDistanceAfterQueries2(int n, vector<vector<int>>& queries) {
        vector<vector<int>> from(n);
        vector<int> f(n);
        iota(f.begin(), f.end(), 0);

        vector<int> ans(queries.size());
        for (int qi = 0; qi < queries.size(); qi++) {
            int l = queries[qi][0], r = queries[qi][1];
            from[r].push_back(l);
            if (f[l] + 1 < f[r]) {
                f[r] = f[l] + 1;
                for (int i = r + 1; i < n; i++) {
                    f[i] = min(f[i], f[i - 1] + 1);
                    for (int j : from[i]) {
                        f[i] = min(f[i], f[j] + 1);
                    }
                }
            }
            ans[qi] = f[n - 1];
        }
        return ans;
    }
};

上一题

下一题

详情