FreakSkipper

P3_D

Dec 2nd, 2020
1,047
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define vi vector<int>
  6. #define vll vector<ll>
  7. #define ll long long
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define mp make_pair
  11. #define ii pair<int, int>
  12.  
  13. #define PRIMO 1000000007
  14.  
  15. const ll oo = 1e18;
  16. const int N = 100;
  17.  
  18. ll G[N + 1][N + 1];
  19. ll D[N + 1][N + 1];
  20.  
  21. void floyd_warshall(int n) {
  22.     for (int i = 0; i < n; i++) {
  23.         for (int j = 0; j < n; j++) {
  24.             if (i == j)
  25.                 D[i][j] = 0;
  26.             else {
  27.                 if (G[i][j])
  28.                     D[i][j] = G[i][j];
  29.                 else
  30.                     D[i][j] = oo;
  31.             }
  32.         }
  33.     }
  34.  
  35.     for (int k = 0; k < n; k++) {
  36.         for (int i = 0; i < n; i++) {
  37.             for (int j = 0; j < n; j++) {
  38.                 D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44.  
  45. int main() {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.  
  49.     int n, m, s, t;
  50.     cin >> n >> m;
  51.  
  52.     for (int i = 0; i < m; i++) {
  53.         int a, b;
  54.         cin >> a >> b;
  55.  
  56.         G[a][b] = 1;
  57.         G[b][a] = 1;
  58.     }
  59.     cin >> s >> t;
  60.  
  61.     floyd_warshall(n);
  62.  
  63.     ll tempo = 0;
  64.     for (int i = 0; i < n; i++) {
  65.         tempo = max(D[s][i] + D[i][t], tempo);
  66.     }
  67.  
  68.     cout << tempo << endl;
  69.  
  70.     return 0;
  71. }
  72.  
  73. // =======================================================
  74.  
  75. // NAO ACEITO
  76.  
  77. #include <bits/stdc++.h>
  78.  
  79. using namespace std;
  80.  
  81. #define vi vector<int>
  82. #define vll vector<ll>
  83. #define ll long long
  84. #define pb push_back
  85. #define eb emplace_back
  86. #define mp make_pair
  87. #define ii pair<int, int>
  88.  
  89. #define PRIMO 1000000007
  90.  
  91. const ll oo = 1e18;
  92. const int N = 100;
  93.  
  94. int main() {
  95.     ios_base::sync_with_stdio(false);
  96.     cin.tie(NULL);
  97.  
  98.     int n, m, s, t;
  99.     cin >> n >> m;
  100.  
  101.     ll G[n+1][n+1];
  102.     ll D[n+1][n+1];
  103.    
  104.     for (int i = 0; i < m; i++) {
  105.         int a, b;
  106.         cin >> a >> b;
  107.  
  108.         G[a][b] = 1;
  109.         G[b][a] = 1;
  110.     }
  111.     cin >> s >> t;
  112.  
  113.     for (int i = 0; i < n; i++) {
  114.         for (int j = 0; j < n; j++) {
  115.             if (i == j)
  116.                 D[i][j] = 0;
  117.             else {
  118.                 if (G[i][j])
  119.                     D[i][j] = G[i][j];
  120.                 else
  121.                     D[i][j] = oo;
  122.             }
  123.         }
  124.     }
  125.  
  126.     for (int k = 0; k < n; k++) {
  127.         for (int i = 0; i < n; i++) {
  128.             for (int j = 0; j < n; j++) {
  129.                 D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
  130.             }
  131.         }
  132.     }
  133.    
  134.     ll tempo = 0;
  135.     for (int i = 0; i < n; i++) {
  136.         tempo = max(D[s][i] + D[i][t], tempo);
  137.     }
  138.  
  139.     cout << tempo << endl;
  140.  
  141.     return 0;
  142. }
RAW Paste Data