Ссылка на засчитанное решение.
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные
В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.
Выходные данные
Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.
Код программы:
|
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 |
#include <cstdlib> #include <iostream> using namespace std; int **a; int main() { int n; cin >> n; a = new int*[n]; for( int i=0 ; i<n ; i++ ) { a[i] = new int [n]; for( int j=0 ; j<n ; j++ ) { cin >> a[i][j]; } } 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] = min(a[i][j], a[i][k]+a[k][j]); } } } } for( int i=0 ; i<n ; i++ ) { for( int j=0 ; j<n ; j++ ) { cout << a[i][j] << ( j+1 == n ? '\n' : ' ' ); } } } |
Считываем число вершин, затем матрицу смежности. Записываем матрицу смежности в массив указателей. Затем для создания матрицы минимальных путей заменяем каждый элемент матрицы на минимум из непосредственного расстояния между вершинами в матрице смежности и расстоянием между ними, проходящим через одну из их общих вершин. Выводим матрицу минимальных путей.
Это не Ваша задача. С чего это вдруг все решили решать задачу Чежеумовой?
Не заметил, что она занята.
Толя тоже. Либо очень привлекательная задача, либо все хотят помочь Ане.