fork(1) download
copy 
  1. //Written by rraj001 :)
  2. #include<bits/stdc++.h>
  3. #define ll int
  4. #define inf 1000000000
  5. #define mp make_pair
  6. #define pb push_back
  7. #define ff first
  8. #define ss second
  9. using namespace std;
  10. vector<ll>adj[112];
  11. vector<ll>d[112];
  12. vector<ll>money[112];
  13. ll budget,n,r,N;
  14. ll dp[112][100011];
  15. ll cal(ll city,ll budget)
  16. {
  17.     ll& ans=dp[city][budget];
  18.     if(ans==-1)
  19.     {
  20.         if(city==N)ans=0;
  21.         else
  22.         {
  23.             ans=inf;
  24.             for(ll i=0;i<adj[city].size();i++)
  25.             {
  26.                 if(money[city][i]<=budget)
  27.                 {
  28.                     ans=min(ans,d[city][i]+cal(adj[city][i],budget-money[city][i]));
  29.                 }
  30.             }
  31.  
  32.         }
  33.     }
  34.     return ans;
  35. }
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45. int main()
  46. {
  47.     //freopen("input.txt","r",stdin);
  48.     std::ios::sync_with_stdio(false);
  49.     ll tc;
  50.     cin>>tc;
  51.     while(tc--)
  52.     {
  53.         cin>>budget>>n>>r;
  54.         for(ll i=0;i<n;i++){adj[i].clear();d[i].clear();money[i].clear();}
  55.         for(ll i=0;i<r;i++)
  56.         {
  57.             ll src,dest,len,t;
  58.             cin>>src>>dest>>len>>t;
  59.             src--;
  60.             dest--;
  61.             adj[src].pb(dest);
  62.             d[src].pb(len);
  63.             money[src].pb(t);
  64.         }
  65.         N=n-1;
  66.         memset(dp,-1,sizeof(dp));
  67.         ll ans=cal(0,budget);
  68.         cout << (ans == inf? -1 : ans) << endl;
  69.  
  70.  
  71.     }
  72.  
  73. }
Success #stdin #stdout 0s 58992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/k0Slqd
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!