Advertisement
tepyotin2

FloydWarshall

Jun 1st, 2025
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long long INF = 1e18;
  6. typedef long long ll;
  7.  
  8. int s1, t1;
  9. int s2, t2;
  10. int n, m;
  11. vector<vector<long long>> dp;
  12. int nv[201][201];
  13. vector<int> ans;
  14.  
  15. int main(){
  16.     //freopen("floydwarshall.in", "r", stdin);
  17.    
  18.     cin >> s1 >> t1;
  19.     cin >> s2 >> t2;
  20.     cin >> n >> m;
  21.     dp.resize(n+1, vector<ll>(n+1, INF));
  22.     for(int i=0; i<m; i++){
  23.         ll a, b, c;
  24.         cin >> a >> b >> c;
  25.         //need to check for minimum because same routes can repeat with different values
  26.         dp[a][b] = min(dp[a][b], c);
  27.         dp[b][a] = min(dp[b][a], c);
  28.         //nv[a][b] = a;
  29.         //nv[b][a] = b;
  30.     }
  31.     for(int i=1; i<=n; i++){
  32.         for(int j=1; j<=n; j++){
  33.             nv[i][j] = j;
  34.             nv[j][i] = i;
  35.         }
  36.     }
  37.     for(int i=1; i<=n; i++){
  38.         dp[i][i] = 0;
  39.     }
  40.     for(int k=1; k<=n; k++){
  41.         for(int i=1; i<=n; i++){
  42.             for(int j=1; j<=n; j++){
  43.                 //nv[i][j] = i;
  44.                 //need to check alll conditions including lexicographical condition within checking infinite and checking node values
  45.                 if(i != k && j != k && dp[i][k] != INF && dp[k][j] != INF){
  46.                     if(dp[i][j] > dp[i][k]+dp[k][j]){
  47.                         dp[i][j] = dp[i][k]+dp[k][j];
  48.                         nv[i][j] = nv[i][k];
  49.                     }else if(dp[i][j] == dp[i][k]+dp[k][j]){
  50.                         if(nv[i][j]>nv[i][k]){
  51.                             nv[i][j] = nv[i][k];
  52.                         }
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     //for(int i=1; i<=n; i++){
  59.         //for(int j=1; j<=n; j++){
  60.             //cout << dp[i][j] << " ";
  61.         //}
  62.         //cout << '\n';
  63.     //}
  64.     cout << dp[s1][t1] << '\n';
  65.     int cur = s1;
  66.     cout << s1;
  67.     //cout << nv[cur][s1] << '\n';
  68.     //int v = 20;
  69.     while(cur != t1){
  70.         cout << " " << nv[cur][t1];
  71.         cur = nv[cur][t1];
  72.     }
  73.     cout << '\n';
  74.     cout << dp[s2][t2] << '\n';
  75.     cur = s2;
  76.     cout << s2;
  77.     //cout << nv[cur][s1] << '\n';
  78.     //v = 20;
  79.     while(cur != t2){
  80.         cout << " " << nv[cur][t2];
  81.         cur = nv[cur][t2];
  82.     }
  83.     cout << '\n';
  84.    
  85.     return 0;
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement