Nik_Perepelov

Надар 5 контет

Oct 20th, 2021 (edited)
161
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // 1
  2. #include <iostream>
  3. #include <limits.h>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     int n, m, k;
  9.     int s, f;
  10.     cin >> n >> m >> k >> s >> f;
  11.     s-=1;
  12.     f-=1;
  13.     int a[m], b[m], weight[m];
  14.     for (int i = 0; i < m; i++) {
  15.         cin >> a[i] >> b[i] >> weight[i];
  16.         a[i] -= 1;
  17.         b[i] -= 1;
  18.     }
  19.     int d[k+1][n];
  20.     for (int i = 0; i < k+1; i++){
  21.         for(int j = 0; j < n; j++){
  22.             d[i][j] = INT_MAX;
  23.         }
  24.     }
  25.     d[0][s] = 0;
  26.     for (int i = 0; i < k; i++) {
  27.         for(int l = 0; l < n; l++)
  28.             d[i + 1][l] = d[i][l];
  29.         for (int j = 0; j < m; j++) {
  30.             if (d[i][a[j]] < INT_MAX) {
  31.                 d[i + 1][b[j]] = min(d[i+1][b[j]], d[i][a[j]] + weight[j]);
  32.             }
  33.         }
  34.     }
  35.     if (d[k][f] == INT_MAX) {
  36.         cout << "-1";
  37.     } else {
  38.         cout << d[k][f];
  39.     }
  40.  
  41.     return 0;
  42. }
  43.  
  44. // 2
  45. #include <iostream>
  46.  
  47. using namespace std;
  48.  
  49. int main() {int n;
  50.     cin >> n;
  51.     int gr[n][n];
  52.     for (int i = 0; i < n; i++){
  53.         for (int j = 0; j < n; j++){
  54.             cin >> gr[i][j];
  55.         }
  56.     }
  57.     for (int k = 0; k < n; k++){
  58.         for (int i = 0; i < n; i++){
  59.             for (int j = 0; j < n; j++){
  60.                 gr[i][j] = min(gr[i][j], gr[i][k] + gr[k][j]);
  61.             }
  62.         }
  63.     }
  64.     for (int i = 0; i < n; i++){
  65.         for (int j = 0; j < n; j++){
  66.             cout << gr[i][j] << " ";
  67.         }
  68.         cout << endl;
  69.     }
  70.     return 0;
  71. }
RAW Paste Data