CSES 1672 Shortest Routes II - Walkthrough

Sample input: $n=4$, $m=3$, $q=5$. Edges: $(1, 2, 5)$, $(1, 3, 9)$, $(2, 3, 3)$. Initialize $dist$: dist[1][2] = dist[2][1] = 5, dist[1][3] = dist[3][1] = 9, dist[2][3] = dist[3][2] = 3, rest infinity. After Floyd-Warshall: dist[1][3] = 8 (route $1 \to 2 \to 3$).

Query $(1, 3)$ returns $8$. This shows how Floyd-Warshall discovers indirect paths that are shorter than direct edges. The algorithm found a better path by routing through vertex $2$.