Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке записано количество вершин графа n (1 ≤ [latex]n[/latex] ≤ 100). В следующих n строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Алгоритм

(взято с Википедии)

Пусть вершины графа [latex]{\displaystyle G=(V,\;E),\;|V|=n}[/latex] пронумерованы от 1 до [latex] {\displaystyle n}[/latex] и введено обозначение [latex]{\displaystyle d_{ij}^{k}}[/latex] для длины кратчайшего пути от [latex] {\displaystyle i}[/latex] до [latex]{\displaystyle j}[/latex], который кроме самих вершин [latex] {\displaystyle i,\;j} [/latex] проходит только через вершины [latex]{\displaystyle 1\ldots k} [/latex]. Очевидно, что [latex]{\displaystyle d_{ij}^{0}} [/latex] — длина (вес) ребра [latex]{\displaystyle (i,\;j)}[/latex], если таковое существует (в противном случае его длина может быть обозначена как [latex]{\displaystyle \infty } [/latex] ).

Существует два варианта значения [latex] {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)[/latex]:

Кратчайший путь между [latex]{\displaystyle i,\;j}[/latex] не проходит через вершину [latex] {\displaystyle k}[/latex], тогда [latex]{\displaystyle d_{ij}^{k}=d_{ij}^{k-1}}[/latex] Существует более короткий путь между [latex]{\displaystyle i,\;j}[/latex], проходящий через [latex]{\displaystyle k}[/latex], тогда он сначала идёт от [latex]{\displaystyle i} [/latex] до [latex] {\displaystyle k} [/latex], а потом от [latex] {\displaystyle k} [/latex] до [latex] {\displaystyle j} [/latex]. В этом случае, очевидно, [latex]{\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}[/latex]

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для [latex]{\displaystyle d_{ij}^{k}}[/latex] имеет вид:

[latex]{\displaystyle d_{ij}^{0}}[/latex] — длина ребра [latex] {\displaystyle (i,\;j);} (i,\;j);[/latex] [latex]{\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}[/latex]

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения [latex]{\displaystyle d_{ij}^{k},} [/latex], [latex]{\displaystyle \forall i,\;j}[/latex] для [latex] {\displaystyle k} [/latex] от 1 до [latex] {\displaystyle n} [/latex]. Полученные значения [latex] {\displaystyle d_{ij}^{n}}[/latex] являются длинами кратчайших путей между вершинами [latex]. {\displaystyle i,\;j.} [/latex].

Код

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com