From
Leetcode
Status
AC
Date
Mar 26, 2024
Tags
Dijkstra
最短路
Difficulty
困难
题面
给你一个有
n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。请你实现一个
Graph 类：Graph(int n, int[][] edges)初始化图有n个节点，并输入初始边。
addEdge(int[] edge)向边集中添加一条边，其中edge = [from, to, edgeCost]。数据保证添加这条边之前对应的两个节点之间没有有向边。
int shortestPath(int node1, int node2)返回从节点node1到node2的路径 最小 代价。如果路径不存在，返回1。一条路径的代价是路径中所有边代价之和。
示例 1：
提示：
1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= fromi, toi, from, to, node1, node2 <= n - 1
1 <= edgeCosti, edgeCost <= 106
- 图中任何时候都不会有重边和自环。
- 调用
addEdge至多100次。
- 调用
shortestPath至多100次。
思路
对于
addEdge，直接把边加入图中即可。
对于 shortestPath，用 Dijkstra 算法计算从起点 start 到终点 end 的最短路长度。题解
邻接矩阵建图 + 朴素 Dijkstra