DiffPush Tier Graphs · Shortest Path Problems O(n^3) · O(1)
A rail company stores its fare table as a square grid: cell (i, j) is the direct fare from platform i to platform j, and a blank (-1) means no direct train. The revenue team must upgrade the table into a true cheapest-fare chart — every pair, via any connections — leaving blanks only where no sequence of trains connects the pair at all.
Input: An n x n matrix where Matrix[i][j] is the direct edge weight from i to j, or -1 if no such edge exists.
Output: Return the updated matrix holding the shortest distance for every ordered pair, with -1 restored where no path exists.
1 <= n <= 500-1 <= Matrix[i][j] <= 10^8, where -1 denotes no edgeThe graph is directed; Matrix[i][i] is 0Input: {"matrix":[[0,25],[-1,0]]}
Output: [[0,25],[-1,0]]
No connection improves any direct fare, and the blank stays blank.
Input: {"matrix":[[0,3,-1],[-1,0,2],[1,-1,0]]}
Output: [[0,3,5],[3,0,2],[1,4,0]]
Connections surface: 0->2 costs 5 via 1, 1->0 costs 3 via 2, and 2->1 costs 4 via 0.