Задача
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные
В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.
Выходные данные
Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 2 0 0 0 0 |
0 0 0 0 |
| 2 |
4 1 2 0 0 2 2 4 4 0 0 1 1 3 4 2 1 |
1 0 0 0 2 2 2 2 0 0 1 0 2 2 2 1 |
| 3 | 2 3 2 1 1 |
3 2 1 1 |
Код программы:
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n; n = in.nextInt(); int [][] a = new int[n][n]; for( int i=0 ; i<n ; i++ ) { for( int j=0 ; j<n ; j++ ) { a[i][j] = in.nextInt(); } } for( int k=0 ; k<n ; k++ ) { for( int i=0 ; i<n ; i++ ) { for( int j=0 ; j<n ; j++ ) { if( i!=j ) { a[i][j] = Math.min(a[i][j], a[i][k]+a[k][j]); } } } } for( int i=0 ; i<n ; i++ ) { for( int j=0 ; j<n ; j++ ) { System.out.print(a[i][j]); if(j+1 == n) { System.out.print("\n"); } else { System.out.print(' '); } } } } } |
Решение
Считываем число вершин, затем матрицу смежности. Записываем матрицу смежности в массив указателей. Затем для создания матрицы минимальных путей заменяем каждый элемент матрицы на минимум из непосредственного расстояния между вершинами в матрице смежности и расстоянием между ними, проходящим через одну из их общих вершин. Выводим матрицу минимальных путей.
Ссылки
Условие задачи на e-olymp.com.
Код решения на ideone.com.