Ссылка на оригинальную статью.
Условие:
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные:
В первой строке записано количество вершин графа [latex]n (1 ≤ n ≤ 100)[/latex]. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают [latex]100[/latex]. На главной диагонали матрицы — всегда нули.
Выходные данные:
Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].
Решение:
Считываем число вершин, затем матрицу смежности. Записываем матрицу смежности в массив. Затем для создания матрицы минимальных путей заменяем каждый элемент матрицы на минимум из непосредственного расстояния между вершинами в матрице смежности и расстоянием между ними, проходящим через одну из их общих вершин. Выводим матрицу минимальных путей.
Тесты:
| Input | Output |
| 4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0 |
0 5 7 13
12 0 2 8 11 16 0 7 4 9 11 0 |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import neko.Lib; /** * ... * @author Zavada Sergey */ class Main { static function main() { var n:Int = Std.parseInt(Sys.stdin().readLine()); var w:Array<Array<Float>> = [for (x in 0...n) [for (y in 0...n) 0]]; for (i in 0...n) { for (j in 0...n) { w[i][j] = Std.parseFloat(Sys.stdin().readLine()); } } for (k in 0...n) { for (i in 0...n) { for (j in 0...n) { w[i][j] = Math.min(w[i][j], w[i][k]+w[k][j]); } } } var output = Sys.stdout(); for (i in 0...n) { for (y in 0...n) { output.writeString(Std.string(w[i][y]) + " "); } output.writeString("\n"); } } } |
- e-olymp 974. Флойд-1 - 13.06.2017
- e-olymp 1872. Снеговики - 13.06.2017
- A155 - 13.05.2017