1import heapq
2
3class Graph:
4    def __init__(self, n, edges):
5        self.n = n
6        self.adj = [[] for _ in range(n)]
7        for u, v, cost in edges:
8            self.adj[u].append((v, cost))
9
10    def addEdge(self, edge):
11        u, v, cost = edge
12        self.adj[u].append((v, cost))
13
14    def shortestPath(self, node1, node2):
15        dist = [float('inf')] * self.n
16        dist[node1] = 0
17        pq = [(0, node1)]
18
19        while pq:
20            curDist, u = heapq.heappop(pq)
21            if u == node2:
22                return curDist
23            if curDist > dist[u]:
24                continue
25            for v, cost in self.adj[u]:
26                if dist[u] + cost < dist[v]:
27                    dist[v] = dist[u] + cost
28                    heapq.heappush(pq, (dist[v], v))
29        return -1
30
31# Demonstration
32if __name__ == "__main__":
33    edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
34    graph = Graph(4, edges)
35    print(graph.shortestPath(3, 2))  # Output: 6
36    print(graph.shortestPath(0, 3))  # Output: -1
37    graph.addEdge([1, 3, 4])
38    print(graph.shortestPath(0, 3))  # Output: 6
39

public class Graph {
    private int n;
    private int[,] dist;

    public Graph(int n, int[][] edges) {
        this.n = n;
        dist = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i, j] = (i == j) ? 0 : int.MaxValue;
        foreach (var edge in edges)
            dist[edge[0], edge[1]] = edge[2];
        FloydWarshall();
    }

    private void FloydWarshall() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue)
                        dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                }
            }
        }
    }

    public void AddEdge(int[] edge) {
        dist[edge[0], edge[1]] = edge[2];
        FloydWarshall();
    }

    public int ShortestPath(int node1, int node2) {
        return dist[node1, node2] == int.MaxValue ? -1 : dist[node1, node2];
    }

    public static void Main(String[] args) {
        int[][] edges = new int[][] { new int[] { 0, 2, 5 }, new int[] { 0, 1, 2 }, new int[] { 1, 2, 1 }, new int[] { 3, 0, 3 } };
        Graph graph = new Graph(4, edges);
        Console.WriteLine(graph.ShortestPath(3, 2)); // Output: 6
        Console.WriteLine(graph.ShortestPath(0, 3)); // Output: -1
        graph.AddEdge(new int[] { 1, 3, 4 });
        Console.WriteLine(graph.ShortestPath(0, 3)); // Output: 6
    }
}