fork(1) download
copy 
  1. /**
  2.  *    author:  longvu
  3.  *    created: 04/20/24 02:12:34
  4. **/
  5. #include<bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define sz(x) ((int)x.size())
  11. #define all(x) (x).begin(), (x).end()
  12. const int INF = 1e18;
  13. const int nax = (int)(501);
  14. const int mod = 1e9 + 7;
  15.  
  16. template<class X, class Y>
  17. bool maximize(X& x, const Y y) {
  18.     if (y > x) {x = y; return true;}
  19.     return false;
  20. }
  21. template<class X, class Y>
  22. bool minimize(X& x, const Y y) {
  23.     if (y < x) {x = y; return true;}
  24.     return false;
  25. }
  26.  
  27. struct Floyd {
  28.     int n, sh_path[nax][nax], next[nax][nax];
  29.     Floyd(int n) : n(n) {
  30.         memset(next, -1, sizeof next);
  31.         memset(sh_path, 0x3f, sizeof sh_path);
  32.         for (int i = 1; i <= n; ++i) {
  33.             sh_path[i][i] = 0;
  34.         }
  35.     }
  36.  
  37.     void add_edge(int u, int v, int val) {
  38.         minimize(sh_path[u][v], val);
  39.         next[u][v] = v;
  40.     }
  41.  
  42.     void solve() {
  43.         for (int e = 1; e <= n; ++e) {
  44.             for (int i = 1; i <= n; ++i) {
  45.                 for (int j = 1; j  <= n; ++j) {
  46.                     if (sh_path[i][e] == INF || sh_path[e][j] == INF) {
  47.                         continue;
  48.                     }
  49.                     if (sh_path[i][e] + sh_path[e][j] < sh_path[i][j]) {
  50.                         sh_path[i][j] = sh_path[i][e] + sh_path[e][j];
  51.                         next[i][j] = next[i][e];
  52.                     }
  53.                 }
  54.             }
  55.             for (int i = 1; i <= e; ++i) {
  56.                 for (int j = 1; j <= e; ++j) {
  57.                     cout << (sh_path[i][j] >= INF ? -1 : sh_path[i][j]) << " ";
  58.                 }
  59.                 cout << '\n';
  60.             }
  61.         }
  62.     }
  63.  
  64.     vector<int> find_path(int u, int v) {
  65.         vector<int> path = {u};
  66.         if (next[u][v] == -1) {
  67.             return {};
  68.         }
  69.         while (u != v) {
  70.             u = next[u][v];
  71.             path.push_back(u);
  72.         }
  73.         return path;
  74.     }
  75. };
  76.  
  77. int32_t main() {
  78.     ios_base::sync_with_stdio(false);
  79.     cin.tie(0);
  80.     int n, m;
  81.     cin >> n >> m;
  82.     Floyd floyd(n);
  83.     for (int i = 1; i <= m; ++i) {
  84.         int u, v, c;
  85.         cin >> u >> v >> c;
  86.         floyd.add_edge(u, v, c);
  87.     }
  88.     floyd.solve();
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 7548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SjfzA4
language:
C++14 (clang 8.0)
created:
12 days 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!