fork 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.     if(city==N)return 0;
  18.     if(dp[city][budget]!=-1)return dp[city][budget];
  19.     ll ans=inf;
  20.     for(ll i=0;i<adj[city].size();i++)
  21.     {
  22.         if(money[city][i]<=budget)
  23.         {
  24.             ans=min(ans,cal(adj[city][i],budget-money[city][i])+d[city][i]);
  25.         }
  26.     }
  27.     return dp[city][budget]=ans;
  28. }
  29. int main()
  30. {
  31.     //freopen("input.txt","r",stdin);
  32.     std::ios::sync_with_stdio(false);
  33.     ll tc;
  34.     cin>>tc;
  35.     while(tc--)
  36.     {
  37.         cin>>budget>>n>>r;
  38.         for(ll i=0;i<=n;i++){adj[i].clear();d[i].clear();money[i].clear();}
  39.         for(ll i=0;i<r;i++)
  40.         {
  41.             ll src,dest,len,t;
  42.             cin>>src>>dest>>len>>t;
  43.             src--;
  44.             dest--;
  45.             adj[src].pb(dest);
  46.             d[src].pb(len);
  47.             money[src].pb(t);
  48.         }
  49.         N=n-1;
  50.         memset(dp,-1,sizeof(dp));
  51.         ll ans=cal(0,budget);
  52.         cout << (ans == inf? -1 : ans) << endl;
  53.  
  54.  
  55.     }
  56.  
  57. }
  58.  
  59.  
Success #stdin #stdout 0s 59816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7ndJXG
language:
C++ (gcc 8.3)
created:
6 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!