Advertisement
Josif_tepe

Untitled

Feb 13th, 2024
651
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <fstream>
  4. #include <vector>
  5. #include <cstring>
  6. //#include <bits/stdc++.h>
  7. using namespace std;
  8. const int maxn = 3005;
  9. const int INF = 1e8;
  10. const int di[] = {-1, 1, 0, 0};
  11. const int dj[] = {0, 0, -1, 1};
  12. struct node {
  13.     int b, T, E;
  14.     node () {}
  15.     node(int _b, int _T, int _E) {
  16.         b = _b;
  17.         T = _T;
  18.         E = _E;
  19.     }
  20.    
  21. };
  22. vector<node> graph[maxn];
  23. int n, m;
  24. int dp[maxn][2002];
  25. int rec(int at, int money_left) {
  26.     if(at == n) {
  27.         return 0;
  28.     }
  29.     if(money_left == 0) {
  30.         return INF;
  31.     }
  32.     if(dp[at][money_left] != -1) {
  33.         return dp[at][money_left];
  34.     }
  35.     int res = INF;
  36.     for(int i = 0; i < (int) graph[at].size(); i++) {
  37.         int neighbour = graph[at][i].b;
  38.         int time = graph[at][i].T;
  39.         int money = graph[at][i].E;
  40.        
  41.         if(money_left >= money) {
  42.             res = min(res, rec(neighbour, money_left - money) + time);
  43.         }
  44.     }
  45.     return dp[at][money_left] = res;
  46. }
  47. int main() {
  48.     ios_base::sync_with_stdio(false);
  49. //    ifstream cin("in.txt");
  50.     int S;
  51.     cin >> S >> n >> m;
  52.    
  53.     for(int i = 0; i < m; i++) {
  54.         int a, b, c, d;
  55.         cin >> a >> b >> c >> d;
  56.         graph[a].push_back(node(b, c, d));
  57.         graph[b].push_back(node(a, c, d));
  58.     }
  59.     memset(dp, -1, sizeof dp);
  60.     int res = INF;
  61.     for(int i = 1; i <= S; i++) {
  62.         res = min(res, rec(1, i));
  63.     }
  64.     if(res >= INF) {
  65.         res = -1;
  66.     }
  67.     cout << res << endl;
  68.    
  69.     return 0;
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement