ccbeginner

UVa 10342

Jan 27th, 2020
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10342
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int edge[100][100];
  6. int dist[100][100];
  7. int dist2[100][100];
  8.  
  9. int32_t main(){
  10.     int n, m, q, cnt = 0;
  11.     while(cin >> n >> m){
  12.         for(int i = 0; i < n; ++i){
  13.             for(int j = 0; j < n; ++j){
  14.                 if(i != j)dist[i][j] = edge[i][j] = 1e8;
  15.                 else dist[i][j] = edge[i][j] = 0;
  16.                 dist2[i][j] = 1e8;
  17.             }
  18.         }
  19.         for(int i = 0; i < m; ++i){
  20.             int u,v,w;
  21.             cin >> u >> v >> w;
  22.             edge[u][v] = w;
  23.             edge[v][u] = w;
  24.             dist2[u][u] = min(dist2[u][u], w*2);
  25.             dist2[v][v] = min(dist2[v][v], w*2);
  26.         }
  27.         for(int k = 0; k < n; ++k){
  28.             for(int i = 0; i < n; ++i){
  29.                 for(int j = 0; j < n; ++j){
  30.                     dist[i][j] = min(dist[i][j], min(edge[i][k], dist[i][k]) + min(edge[k][j], dist[k][j]));
  31.                 }
  32.             }
  33.         }
  34.         for(int k = 0; k < n; ++k){
  35.             for(int i = 0; i < n; ++i){
  36.                 for(int j = 0; j < n; ++j){
  37.                     int ik = (dist[i][k] == edge[i][k])? dist2[i][k] : min(edge[i][k], dist2[i][k]);//second shortest path between i,k
  38.                     int kj = (dist[k][j] == edge[k][j])? dist2[k][j] : min(edge[k][j], dist2[k][j]);//second shortest path between k,j
  39.                     if(dist[i][j] != dist[i][k] + dist[k][j])dist2[i][j] = min(dist2[i][j], dist[i][k] + dist[k][j]);
  40.                     dist2[i][j] = min(dist2[i][j], ik + dist[k][j]);
  41.                     dist2[i][j] = min(dist2[i][j], dist[i][k] + kj);
  42.                 }
  43.             }
  44.         }
  45.         /*debugsssss
  46.         cout << "dist\n";
  47.         for(int i = 0; i < n; ++i){
  48.             for(int j = 0; j < n; ++j){
  49.                 cout << dist[i][j] << ' ';
  50.             }
  51.             cout << endl;
  52.         }
  53.         cout << endl << "dist2\n";
  54.         for(int i = 0; i < n; ++i){
  55.             for(int j = 0; j < n; ++j){
  56.                 cout << dist2[i][j] << ' ';
  57.             }
  58.             cout << endl;
  59.         }
  60.         cout << endl << "bet\n";
  61.         for(int i = 0; i < n; ++i){
  62.             for(int j = 0; j < n; ++j){
  63.                 (dist[i][j] == edge[i][j])? cout << dist2[i][j] : cout << min(edge[i][j], dist2[i][j]);
  64.                 //cout << edge[i][j];
  65.                 cout << ' ';
  66.             }
  67.             cout << endl;
  68.         }
  69.         */
  70.         cout << "Set #" << ++cnt << '\n';
  71.         cin >> q;
  72.         while(q--){
  73.             int u,v;
  74.             cin >> u >> v;
  75.             int ans = dist2[u][v];
  76.             if(ans == 1e8)cout << "?\n";
  77.             else cout << ans << '\n';
  78.         }
  79.     }
  80.     return 0 ;
  81. }
RAW Paste Data