Nik_Perepelov

5 контест Настя

Oct 20th, 2021
1,018
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <limits.h>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct edge{
  8.     int from;
  9.     int to;
  10.     int weight;
  11. };
  12.  
  13. int main() {
  14.     int n, m, k, start, finish;
  15.     cin >> n >> m >> k >> start >> finish;
  16.     vector <edge> g(m);
  17.     for (int i = 0; i < m; i++) {
  18.         cin >> g[i].from >> g[i].to >> g[i].weight;
  19.         g[i].to -= 1;
  20.         g[i].from -= 1;
  21.     }
  22.     vector<vector<int>> d(k+1, vector<int> (n, INT_MAX));
  23.     d[0][start - 1] = 0;
  24.     for (int i = 0; i < k; i++) {
  25.         d[i + 1] = d[i];
  26.         for (int j = 0; j < m; j++) {
  27.             if (d[i][g[j].from] < INT_MAX)
  28.                 d[i + 1][g[j].to] = min(d[i+1][g[j].to], d[i][g[j].from] + g[j].weight);
  29.         }
  30.  
  31.     }
  32.     if (d[k][finish - 1] == INT_MAX)
  33.         cout << -1;
  34.     else
  35.         cout << d[k][finish - 1];
  36.     return 0;
  37. }
RAW Paste Data