1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Graph:
def __init__(self, n: int, edges: List[List[int]]):
self.graph = [set() for _ in range(n)]
for from_node, to_node, cost in edges:
self.graph[from_node].add((cost, to_node))
self.n = n
def addEdge(self, edge: List[int]) -> None:
from_node, to_node, cost = edge
self.graph[from_node].add((cost, to_node))
def shortestPath(self, node1: int, node2: int) -> int:
dis_table = [int(1e9) for _ in range(self.n)]
dis_table[node1] = 0
priority_queue = []
heapq.heappush(priority_queue, (0, node1))
while priority_queue:
current_cost, current_node = heapq.heappop(priority_queue)
if current_node == node2:
return current_cost
if dis_table[current_node] < current_cost:
continue
for cost, adjust_node in self.graph[current_node]:
new_cost = current_cost + cost
if new_cost < dis_table[adjust_node]:
dis_table[adjust_node] = new_cost
heapq.heappush(priority_queue, (new_cost, adjust_node))
return -1
|
