fork download 
  1. #include <bits/stdc++.h>
  2. #define fo(i,x,y) for (int i = x; i < y; i++)
  3. #define fd(i,x,y) for(int i = x; i>= y; i--)
  4. #define ll long long
  5. #define clr(A,x) memset(A, x, sizeof A)
  6. #define pb push_back
  7. #define mod 1000000007
  8. #define debug(x) cout <<#x << " = " << x << endl
  9.  
  10. using namespace std;
  11. vector<int> lista[105];
  12. int din,n;
  13. int length[105][105];
  14. int peaje[105][105];
  15. bool used[105][10005];
  16. int dp[105][10005];
  17. const int MAXN=1e9;
  18. int f(int padre,int dinero)
  19. {
  20.     if(padre==n)
  21.     {
  22.         return 0;
  23.     }
  24.     if(used[padre][dinero])
  25.     {
  26.         return dp[padre][dinero];
  27.     }
  28.     int mini=MAXN;
  29.     fo(i,0,lista[padre].size())
  30.     {
  31.         int hijo=lista[padre][i];
  32.         if(dinero+peaje[padre][hijo]<=din)
  33.         {
  34.             mini=min(mini,f(hijo,dinero+peaje[padre][hijo])+length[padre][hijo]);
  35.         }
  36.     }
  37.     used[padre][dinero]=1;
  38.     dp[padre][dinero]=mini;
  39.     return mini;
  40. }
  41. int main()
  42. {
  43.     cin.sync_with_stdio(false);
  44.     //freopen("D:\input.txt","r",stdin);
  45.     int t;
  46.     cin>>t;
  47.     fo(q,0,t)
  48.     {
  49.         memset(dp,0,sizeof(dp));
  50.         memset(used,0,sizeof(used));
  51.         fo(i,0,105)
  52.         {
  53.             lista[i].clear();
  54.         }
  55.         memset(length,1000000,sizeof(length));
  56.         memset(peaje,1000000,sizeof(peaje));
  57.         cin>>din>>n;
  58.         int r;
  59.         cin>>r;
  60.         fo(i,0,r)
  61.         {
  62.             int x,y,z,w;
  63.             cin>>x>>y>>z>>w;
  64.             lista[x].pb(y);
  65.             length[x][y]=min(length[x][y],z);
  66.             peaje[x][y]=min(peaje[x][y],w);
  67.         }
  68.         int ans=f(1,0);
  69.         if(ans==MAXN)
  70.         {
  71.             cout<<-1<<'\n';
  72.         }
  73.         else
  74.         {
  75.             cout<<ans<<'\n';
  76.         }
  77.     }
  78. }
  79.  
Success #stdin #stdout 0s 8672KB
comments (?)
stdin 
2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
stdout 
11
-1
https://ideone.com/0d3F70
language:
C++ (gcc 8.3)
created:
9 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!