Advertisement
Josif_tepe

Untitled

Nov 7th, 2022
771
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <fstream>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int graph[555][555];
  8. int shortest_path[555][555];
  9. const int INF = 1e9;
  10. int main()
  11. {
  12.     int n, m;
  13.     cin >> n >> m;
  14.     for(int i = 1; i <= n; i++) {
  15.         for(int j = 1; j <= n; j++) {
  16.             if(i == j) {
  17.                 graph[i][j] = 0;
  18.             }
  19.             else {
  20.                 graph[i][j] = 1e9;
  21.             }
  22.         }
  23.     }
  24.     for(int i = 0; i < m; i++) {
  25.         int a, b, c;
  26.         cin >> a >> b >> c;
  27.         graph[a][b] = c;
  28.     }
  29.    
  30.     for(int i = 1; i <= n; i++) {
  31.         for(int j = 1; j <= n; j++) {
  32.             shortest_path[i][j] = graph[i][j];
  33.         }
  34.     }
  35.     cout << endl;
  36.    
  37.     for(int k = 1; k <= n; k++) {
  38.         for(int i = 1; i <= n; i++) {
  39.             for(int j = 1; j <= n; j++) {
  40.                 if(shortest_path[i][k] != INF and shortest_path[k][j] != INF) {
  41.                     shortest_path[i][j] = min(shortest_path[i][j], shortest_path[i][k] + shortest_path[k][j]);
  42.                 }
  43.             }
  44.         }
  45.     }
  46.    
  47.     for(int i = 1; i <= n; i++) {
  48.         for(int j = 1; j <= n; j++) {
  49.             cout << shortest_path[i][j] << " ";
  50.         }
  51.         cout << endl;
  52.     }
  53.     return 0;
  54. }
  55.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement