2642.设计可以求最短路径的图类

链接：2642.设计可以求最短路径的图类
难度：Hard
标签：图、设计、最短路、堆（优先队列）
简介：请你实现一个 Graph 类。

题解 1 - python

• 编辑时间：2024-03-26
• 执行用时：349ms
• 内存消耗：20.49MB
• 编程语言：python
• 解法介绍：图的最短路。

class Node:
    def __init__(self):
        self.f = []
        self.t = []
class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.nodes = [Node() for _ in range(n)]
        for [f, t, cost] in edges:
            self.nodes[f].t.append((t, cost))
            self.nodes[t].f.append((f, cost))
    def addEdge(self, edge: List[int]) -> None:
        self.nodes[edge[0]].t.append((edge[1], edge[2]))
    def shortestPath(self, node1: int, node2: int) -> int:
        q = [(0, node1)]
        used = {}
        while q: 
            cost, node = heappop(q)
            if node == node2: return cost
            for next_node, next_cost in self.nodes[node].t:
                cost2 = next_cost + cost
                if next_node not in used or used[next_node] > cost2:
                    heappush(q, (cost2, next_node))
                    used[next_node] = cost2
        return -1