Problem#
有一個有向帶權圖有 $n$ 個節點標號從 0 到 n-1，要你實作一個 Graph class 可以輸入一張圖，包含 n 個點和 edges 邊，並且能提供求點 a 到點 b 的最短路徑，並且能隨時加邊。
要實作三個 function:
Graph(int n, int[][] edges): 建立圖addEdge(int[] edge): 加入邊到圖中int shortestPath(int node1, int node2): 回傳node1到node2的最短距離，如果無法到達則回傳-1
測資限制#
- 點數: $1 \le n \le 100$
- 邊數: $0 \le e \le n\times(n-1)$
- $1 \le cost \le 10^6$
addEdge呼叫次數: $a \le 100$shortestPath呼叫次數: $s \le 100$
想法#
最短路裸題
AC Code#
- 時間複雜度: $\mathcal{O}(n+a+s \cdot n\log{e})$
- 空間複雜度: $\mathcal{O}(n+e+a)$
心得#
這題應該不算 Hard 才對