fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define endl "\n"
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define yes cout<<"YES"<<"\n"
  7. #define no cout<<"NO"<<"\n"
  8. const ll N = 510; 
  9. const ll INF = 1e9+10;
  10. using namespace std;
  11.  
  12. ll dist[N][N];
  13.  
  14. int main() {
  15.     // directed graph
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(0);
  18.     // set all dist to INF
  19.     for(ll i = 0; i < N; i++){
  20.         for(ll j = 0; j < N; j++) {
  21.             if(i == j) dist[i][j] = 0;
  22.             else dist[i][j] = INF;
  23.         }
  24.     }
  25.     ll n, m; cin >> n >> m;
  26.     for(ll i = 0; i < m; i++) {
  27.         ll x, y, wt;
  28.         cin >> x >> y >> wt;
  29.         dist[x][y] = wt;
  30.     }
  31.     // main algorithm
  32.     for(ll k = 1; k <= n; k++) 
  33.         for(ll i = 1; i <= n; i++) 
  34.             for(ll j = 1; j <= n; j++) {
  35.                 if(dist[i][k] != INF && dist[k][j] != INF)
  36.                     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  37.             }
  38.  
  39.     // display
  40.     for(ll i = 1; i <= n; i++) {
  41.         for(ll j = 1; j <= n; j++) {
  42.             dist[i][j] == INF ? cout << "I" << " " : cout << dist[i][j] << " ";
  43.         }
  44.         cout << endl;
  45.     }
  46. }
Success #stdin #stdout 0.01s 5664KB
comments (?)
stdin
copy 
6 9
1 2 1
1 3 5
2 3 2
3 5 2
2 5 1
2 4 2
4 5 3
4 6 1
5 6 2
stdout
copy 
0 1 3 3 2 4 
I 0 2 2 1 3 
I I 0 I 2 4 
I I I 0 3 1 
I I I I 0 2 
I I I I I 0
https://ideone.com/i8eLio
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!