class Graph {
public:
Graph(int n, vector<vector<int>>& edges) {
}
void addEdge(vector<int> edge) {
}
int shortestPath(int node1, int node2) {
}
};
/**
* Your Graph object will be instantiated and called as such:
* Graph* obj = new Graph(n, edges);
* obj->addEdge(edge);
* int param_2 = obj->shortestPath(node1,node2);
*/
use std::collections::BinaryHeap;
struct Graph {
g: Vec<Vec<(usize, i32)>>, // 邻接表
}
impl Graph {
fn new(n: i32, edges: Vec<Vec<i32>>) -> Self {
let mut g = vec![vec![]; n as usize];
for e in &edges {
g[e[0] as usize].push((e[1] as usize, e[2]));
}
Self { g }
}
fn add_edge(&mut self, e: Vec<i32>) {
self.g[e[0] as usize].push((e[1] as usize, e[2]));
}
fn shortest_path(&self, node1: i32, node2: i32) -> i32 {
let start = node1 as usize;
let end = node2 as usize;
// dis[i] 表示从起点 start 出发，到节点 i 的最短路长度
let mut dis = vec![i32::MAX; self.g.len()];
dis[start] = 0;
let mut h = BinaryHeap::new();
h.push((0, start));
while let Some((d, x)) = h.pop() {
let d = -d;
if x == end { // 计算出从起点到终点的最短路长度
return d;
}
if d > dis[x] { // x 之前出堆过，无需更新邻居的最短路
continue;
}
for &(y, w) in &self.g[x] {
if d + w < dis[y] {
dis[y] = d + w; // 更新最短路长度
h.push((-dis[y], y)); // 加负号变最小堆
}
}
}
-1 // 无法到达终点
}
}
/**
* Your Graph object will be instantiated and called as such:
* let obj = Graph::new(n, edges);
* obj.add_edge(edge);
* let ret_2: i32 = obj.shortest_path(node1, node2);
*/
struct Graph {
g: Vec<Vec<i32>>, // 邻接矩阵
}
impl Graph {
fn new(n: i32, edges: Vec<Vec<i32>>) -> Self {
let n = n as usize;
let mut g = vec![vec![i32::MAX / 2; n]; n];
for e in &edges {
g[e[0] as usize][e[1] as usize] = e[2]; // 添加一条边（题目保证没有重边）
}
Self { g }
}
fn add_edge(&mut self, e: Vec<i32>) {
self.g[e[0] as usize][e[1] as usize] = e[2]; // 添加一条边（题目保证这条边之前不存在）
}
fn shortest_path(&self, node1: i32, node2: i32) -> i32 {
let n = self.g.len();
let start = node1 as usize;
let end = node2 as usize;
// dis[i] 表示从起点 start 出发，到节点 i 的最短路长度
let mut dis = vec![i32::MAX / 2; self.g.len()];
dis[start] = 0;
let mut vis = vec![false; n];
loop {
let mut x = n;
for i in 0..n {
if !vis[i] && (x == n || dis[i] < dis[x]) {
x = i;
}
}
if x == n || dis[x] == i32::MAX / 2 { // 所有从 start 能到达的点都被更新了
return -1; // 无法到达终点
}
if x == end { // 找到终点，提前退出
return dis[x];
}
vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
for y in 0..n {
dis[y] = dis[y].min(dis[x] + self.g[x][y]); // 更新最短路长度
}
}
}
}
/**
* Your Graph object will be instantiated and called as such:
* let obj = Graph::new(n, edges);
* obj.add_edge(edge);
* let ret_2: i32 = obj.shortest_path(node1, node2);
*/
class Graph {
private static final int INF = Integer.MAX_VALUE / 3; // 防止更新最短路时加法溢出
private int[][] d;
public Graph(int n, int[][] edges) {
d = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
for (int i = 0; i < n; ++i) {
Arrays.fill(d[i], INF);
d[i][i] = 0;
}
for (var e : edges)
d[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边和自环）
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
public void addEdge(int[] e) {
int x = e[0], y = e[1], w = e[2], n = d.length;
if (w >= d[x][y]) // 无需更新
return;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = Math.min(d[i][j], d[i][x] + w + d[y][j]);
}
public int shortestPath(int start, int end) {
int ans = d[start][end];
return ans < INF / 3 ? ans : -1;
}
}
/**
* Your Graph object will be instantiated and called as such:
* Graph obj = new Graph(n, edges);
* obj.addEdge(edge);
* int param_2 = obj.shortestPath(node1,node2);
*/
class Graph:
def __init__(self, n: int, edges: List[List[int]]):
d = [[inf] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for x, y, w in edges:
d[x][y] = w # 添加一条边（输入保证没有重边和自环）
for k in range(n):
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
self.d = d
def addEdge(self, e: List[int]) -> None:
d = self.d
n = len(d)
x, y, w = e
if w >= d[x][y]: # 无需更新
return
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j], d[i][x] + w + d[y][j])
def shortestPath(self, start: int, end: int) -> int:
ans = self.d[start][end]
return ans if ans < inf else -1
# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)
const inf = math.MaxInt / 3 // 防止更新最短路时加法溢出
type Graph [][]int
func Constructor(n int, edges [][]int) Graph {
d := make([][]int, n) // 邻接矩阵
for i := range d {
d[i] = make([]int, n)
for j := range d[i] {
if j != i {
d[i][j] = inf // 初始化为无穷大，表示 i 到 j 没有边
}
}
}
for _, e := range edges {
d[e[0]][e[1]] = e[2] // 添加一条边（输入保证没有重边和自环）
}
for k := range d {
for i := range d {
for j := range d {
d[i][j] = min(d[i][j], d[i][k]+d[k][j])
}
}
}
return d
}
func (d Graph) AddEdge(e []int) {
x, y, w := e[0], e[1], e[2]
if w >= d[x][y] { // 无需更新
return
}
for i := range d {
for j := range d {
d[i][j] = min(d[i][j], d[i][x]+w+d[y][j])
}
}
}
func (d Graph) ShortestPath(start, end int) int {
ans := d[start][end]
if ans == inf {
return -1
}
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
/**
* Your Graph object will be instantiated and called as such:
* obj := Constructor(n, edges);
* obj.AddEdge(edge);
* param_2 := obj.ShortestPath(node1,node2);
*/
const inf = math.MaxInt / 2 // 防止更新最短路时加法溢出
type Graph [][]int
func Constructor(n int, edges [][]int) Graph {
g := make([][]int, n) // 邻接矩阵
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf // 初始化为无穷大，表示 i 到 j 没有边
}
}
for _, e := range edges {
g[e[0]][e[1]] = e[2] // 添加一条边（输入保证没有重边）
}
return g
}
func (g Graph) AddEdge(e []int) {
g[e[0]][e[1]] = e[2] // 添加一条边（输入保证这条边之前不存在）
}
// 朴素 Dijkstra 算法
func (g Graph) ShortestPath(start, end int) int {
n := len(g)
dis := make([]int, n) // 从 start 出发，到各个点的最短路，如果不存在则为无穷大
for i := range dis {
dis[i] = inf
}
dis[start] = 0
vis := make([]bool, n)
for {
// 找到当前最短路，去更新它的邻居的最短路，
// 根据数学归纳法，dis[x] 一定是最短路长度
x := -1
for i, b := range vis {
if !b && (x < 0 || dis[i] < dis[x]) {
x = i
}
}
if x < 0 || dis[x] == inf { // 所有从 start 能到达的点都被更新了
return -1
}
if x == end { // 找到终点，提前退出
return dis[x]
}
vis[x] = true // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
for y, w := range g[x] {
dis[y] = min(dis[y], dis[x]+w) // 更新最短路长度
}
}
}
func min(a, b int) int { if b < a { return b }; return a }
/**
* Your Graph object will be instantiated and called as such:
* obj := Constructor(n, edges);
* obj.AddEdge(edge);
* param_2 := obj.ShortestPath(node1,node2);
*/
class Graph:
def __init__(self, n: int, edges: List[List[int]]):
g = [[inf] * n for _ in range(n)] # 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
for x, y, w in edges:
g[x][y] = w # 添加一条边（输入保证没有重边）
self.g = g
def addEdge(self, e: List[int]) -> None:
self.g[e[0]][e[1]] = e[2] # 添加一条边（输入保证这条边之前不存在）
# 朴素 Dijkstra 算法
def shortestPath(self, start: int, end: int) -> int:
n = len(self.g)
dis = [inf] * n # 从 start 出发，到各个点的最短路，如果不存在则为无穷大
dis[start] = 0
vis = [False] * n
while True: # 至多循环 n 次
# 找到当前最短路，去更新它的邻居的最短路
# 根据数学归纳法，dis[x] 一定是最短路长度
x = -1
for i, (b, d) in enumerate(zip(vis, dis)):
if not b and (x < 0 or d < dis[x]):
x = i
if x < 0 or dis[x] == inf: # 所有从 start 能到达的点都被更新了
return -1
if x == end: # 找到终点，提前退出
return dis[x]
vis[x] = True # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
for y, w in enumerate(self.g[x]):
if dis[x] + w < dis[y]:
dis[y] = dis[x] + w # 更新最短路长度
# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)
class Graph {
private static final int INF = Integer.MAX_VALUE / 2; // 防止更新最短路时加法溢出
private int[][] g;
public Graph(int n, int[][] edges) {
g = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
for (int i = 0; i < n; ++i)
Arrays.fill(g[i], INF);
for (var e : edges)
g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边）
}
public void addEdge(int[] e) {
g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证这条边之前不存在）
}
// 朴素 Dijkstra 算法
public int shortestPath(int start, int end) {
int n = g.length;
var dis = new int[n]; // 从 start 出发，到各个点的最短路，如果不存在则为无穷大
Arrays.fill(dis, INF);
dis[start] = 0;
var vis = new boolean[n];
for (;;) {
// 找到当前最短路，去更新它的邻居的最短路
// 根据数学归纳法，dis[x] 一定是最短路长度
int x = -1;
for (int i = 0; i < n; ++i)
if (!vis[i] && (x < 0 || dis[i] < dis[x]))
x = i;
if (x < 0 || dis[x] == INF) // 所有从 start 能到达的点都被更新了
return -1;
if (x == end) // 找到终点，提前退出
return dis[x];
vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
for (int y = 0; y < n; ++y)
dis[y] = Math.min(dis[y], dis[x] + g[x][y]); // 更新最短路长度
}
}
}
/**
* Your Graph object will be instantiated and called as such:
* Graph obj = new Graph(n, edges);
* obj.addEdge(edge);
* int param_2 = obj.shortestPath(node1,node2);
*/
