Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные
В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.
Выходные данные
Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.
Сам алгоритм хорошо описан на wikipedia
А вот сам код
|
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 |
#include <iostream> using namespace std; int main(){ int n; cin >> n; int w[n][n]; for( int i=0 ; i<n ; i++ ){ for( int j=0 ; j<n ; j++ ){ cin >> w[i][j]; } } for( int k=0 ; k<n ; k++ ){ for( int i=0 ; i<n ; i++ ){ for( int j=0 ; j<n ; j++ ){ w[i][j] = min(w[i][j], w[i][k]+w[k][j]); } } } for( int i=0 ; i<n ; i++ ){ for( int j=0 ; j<n ; j++ ){ cout << w[i][j] << " "; } cout<<endl; } } |
- Условие на e-olymp.com
- Решение на e-olymp.com
- Код на ideone.com
Работает шустро. Молодец. Но можно ещё быстрее. А так просто повторяет код решения выполненного Зелинским.
Название я Вам сам поправил, а остальное (ключевые слова, тесты пояснения к коду и т.п.) Вы уж как-нибудь сами доделайте. Чтобы через годы не стеснятся качества оформления.