列表

详情

2714. 找到最短路径的 K 次跨越

现给定一个正整数 n ，它表示一个 索引从 0 开始的无向带权连接图 的节点数，以及一个 索引从 0 开始的二维数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间存在权重为 wi 的边。

还给定两个节点 s 和 d ，以及一个正整数 k ，你的任务是找到从 s 到 d 的 最短 路径，但你可以 最多 跨越 k 条边。换句话说，将 最多 k 条边的权重设为 0，然后找到从 s 到 d 的 最短 路径。

返回满足给定条件的从 s 到 d 的 最短 路径的长度。

 

示例 1：

输入：n = 4, edges = [[0,1,4],[0,2,2],[2,3,6]], s = 1, d = 3, k = 2
输出：2
解释：在这个例子中，只有一条从节点1（绿色节点）到节点3（红色节点）的路径，即（1->0->2->3），其长度为4 + 2 + 6 = 12。现在我们可以将两条边的权重设为 0，即将蓝色边的权重设为 0，那么路径的长度就变为 0 + 2 + 0 = 2。可以证明 2 是我们在给定条件下能够达到的最小路径长度。

示例 2：

输入：n = 7, edges = [[3,1,9],[3,2,4],[4,0,9],[0,5,6],[3,6,2],[6,0,4],[1,2,4]], s = 4, d = 1, k = 2
输出：6
解释：在这个例子中，有两条从节点4（绿色节点）到节点1（红色节点）的路径，分别是（4->0->6->3->2->1）和（4->0->6->3->1）。第一条路径的长度为 9 + 4 + 2 + 4 + 4 = 23，第二条路径的长度为 9 + 4 + 2 + 9 = 24。现在，如果我们将蓝色边的权重设为 0，那么最短路径的长度就变为 0 + 4 + 2 + 0 = 6。可以证明 6 是我们在给定条件下能够达到的最小路径长度。

示例 3：

输入：n = 5, edges = [[0,4,2],[0,1,3],[0,2,1],[2,1,4],[1,3,4],[3,4,7]], s = 2, d = 3, k = 1
输出：3
解释：在这个例子中，从节点2（绿色节点）到节点3（红色节点）有4条路径，分别是（2->1->3）、（2->0->1->3）、（2->1->0->4->3）和（2->0->4->3）。前两条路径的长度为4 + 4 = 1 + 3 + 4 = 8，第三条路径的长度为4 + 3 + 2 + 7 = 16，最后一条路径的长度为1 + 2 + 7 = 10。现在，如果我们将蓝色边的权重设为 0，那么最短路径的长度就为1 + 2 + 0 = 3。可以证明在给定条件下，3 是我们能够达到的最小路径长度。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int shortestPathWithHops(int n, vector<vector<int>>& edges, int s, int d, int k) { } };

cpp 解法, 执行用时: 508 ms, 内存消耗: 84.8 MB, 提交时间: 2023-10-22 10:41:35 

typedef pair<int, int> PII;
typedef tuple<int, int, int> TIII;


class Solution {
public:
    int shortestPathWithHops(int n, vector<vector<int>>& edges, int s, int d, int k) {
        vector<vector<PII>> g(n);
        for (auto& edge : edges) {
            int a = edge[0], b = edge[1], c = edge[2];
            g[a].emplace_back(b, c);
            g[b].emplace_back(a, c);
        }
        vector<vector<int>> dist(n, vector<int>(k + 1, INT_MAX));
        dist[s][0] = 0;
        vector<vector<bool>> seen(n, vector<bool>(k + 1, false));
        priority_queue<TIII, vector<TIII>, greater<TIII>> pq;
        pq.emplace(0, s, 0);

        while (!pq.empty()) {
            auto [td, u, tk] = pq.top();
            pq.pop();
            if (seen[u][tk]) continue;
            seen[u][tk] = true;
            for (auto& [v, nd] : g[u]) {
                if (dist[v][tk] > td + nd) {
                    dist[v][tk] = td + nd;
                    pq.emplace(td + nd, v, tk);
                }
                if (tk < k and dist[v][tk + 1] > td) {
                    dist[v][tk + 1] = td;
                    pq.emplace(td, v, tk + 1);
                }
            }
        }
        return *min_element(dist[d].begin(), dist[d].end());
    }
};

python3 解法, 执行用时: 1316 ms, 内存消耗: 24.1 MB, 提交时间: 2023-10-22 10:41:21 

class Solution:
    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:
        e = defaultdict(set)
        for u,v,w in edges:
            e[u].add((v,w))
            e[v].add((u,w))
        dis = [[float('inf') for _ in range(k + 1)] for _ in range(n)]
        dis[s][0] = 0
        h = [[0,s,0]]
        ans = float('inf')
        while h:
            c,cur,cnt = heappop(h)
            if dis[cur][cnt] < c:
                continue
            for nxt,cost in e[cur]:
                if cnt + 1 <= k and dis[nxt][cnt + 1] > c:
                    dis[nxt][cnt + 1] = c
                    heappush(h,[c,nxt,cnt + 1])
                nc = cost + c
                if dis[nxt][cnt] > nc:
                    dis[nxt][cnt] = nc
                    heappush(h,[nc,nxt,cnt])
        
        for i in range(k + 1):
            ans = min(ans,dis[d][i])
        return ans

上一题

© 2024 leetcode.cn