Advertisement
tepyotin2

Shortest Routes II

May 31st, 2025
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const long long INF = 1e18;
  7.  
  8. struct Routes{
  9.     int from;
  10.     int to;
  11.     ll weight;
  12. };
  13.  
  14. int n, m, q;
  15. Routes route[250001];
  16. vector<vector<ll>> dp;
  17.  
  18. int main(){
  19.     //freopen("routesII.in", "r", stdin);
  20.    
  21.     cin >> n >> m >> q;
  22.     dp.resize(n+1, vector<ll>(n+1, INF));
  23.     //for(int i=1; i<=n; i++){
  24.         //for(int j=1; j<=n; j++){
  25.             //dp[i][j] = LLONG_MAX;
  26.         //}
  27.     //}
  28.     for(int i=0; i<m; i++){
  29.         cin >> route[i].from >> route[i].to >> route[i].weight;
  30.         //cout << route[i].from << ", " << route[i].to << ", " << route[i].weight << '\n';
  31.         dp[route[i].from][route[i].to] = min(dp[route[i].from][route[i].to], route[i].weight);
  32.         dp[route[i].to][route[i].from] = min(dp[route[i].to][route[i].from], route[i].weight);
  33.     }
  34.     //memset(dp, 1e9, sizeof(dp));
  35.     //dp[1][1] = 1e9;
  36.     for(int i=1; i<=n; i++){
  37.         dp[i][i] = 0;
  38.     }
  39.     for(int k=1; k<=n; k++){
  40.         for(int i=1; i<=n; i++){
  41.             for(int j=1; j<=n; j++){
  42.                 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
  43.             }
  44.         }
  45.     }
  46.     //for(int i=1; i<=n; i++){
  47.         //for(int j=1; j<=n; j++){
  48.             //cout << dp[i][j] << " ";
  49.         //}
  50.         //cout << '\n';
  51.     //}
  52.     for(int i=0; i<q; i++){
  53.         int a, b;
  54.         cin >> a >> b;
  55.         if(dp[a][b] == INF){
  56.             cout << -1 << '\n';
  57.         }else{
  58.             cout << dp[a][b] << '\n';
  59.         }
  60.     }
  61.    
  62.     return 0;
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement