fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define node pair<ll, pair<ll, ll > >
  5. struct road{
  6.     ll dest, money, length; 
  7. };
  8. ll dp[10001][101];
  9.  
  10. void solve()
  11. {
  12.     vector<road> g[101];
  13.     ll money, cities,roads;
  14.     cin>>money>>cities>>roads;
  15.     for(ll i=0;i<roads;i++)
  16.     {
  17.         ll u, v, l, t;
  18.         cin>>u>>v>>l>>t;
  19.         road r;
  20.         r.dest = v, r.length = l, r.money = t;
  21.         g[u].push_back(r);
  22.     } 
  23.  
  24.     priority_queue<node , vector<node >, greater<node > > pq;
  25.     // length, city, money
  26.     dp[0][1] = 0;
  27.     pq.push({0, {1, 0}});
  28.     ll ans= INT_MAX;
  29.     while(!pq.empty())
  30.     {
  31.         node fr=pq.top();
  32.         pq.pop();
  33.         if (fr.second.second > money)
  34.         {
  35.             continue;
  36.         }
  37.         if (fr.second.first == cities && fr.second.second <= money)
  38.         {
  39.             ans = min(fr.first, ans);
  40.             dp[fr.second.second][fr.second.first] = fr.first;
  41.         }
  42.         for(int i=0;i<g[fr.second.first].size();i++)
  43.         {
  44.             road r = g[fr.second.first][i];
  45.             if (dp[fr.second.second][fr.second.first] + r.length < dp[fr.second.second + r.money][r.dest])
  46.             {
  47.                 dp[fr.second.second + r.money][r.dest] = dp[fr.second.second][fr.second.first] + r.length;
  48.                 pq.push({dp[fr.second.second + r.money][r.dest], {r.dest, fr.second.second + r.money}});
  49.             }
  50.         }
  51.     }
  52.     if(ans == INT_MAX)
  53.     {
  54.         cout<<-1<<endl;
  55.     }
  56.     else
  57.     {
  58.         cout<<ans<<endl;
  59.     }
  60.     for (ll i = 0; i <= 10001; i++)
  61.         for (ll j = 0; j <= 100; j++)
  62.         {
  63.             dp[i][j] = INT_MAX;
  64.         }
  65. }
  66. int main()
  67. {
  68.     ios_base::sync_with_stdio(0);
  69.     cin.tie(0), cout.tie(0);
  70.     ll t;
  71.     cin>>t;
  72.     for (ll i = 0; i <= 10001; i++)
  73.     for (int j = 0; j <= 100; j++)
  74.         {
  75.             dp[i][j] = INT_MAX;
  76.         }
  77.     while(t--)
  78.     {
  79.         solve();
  80.     }
  81. }
Success #stdin #stdout 0s 10932KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d0lygR
language:
C++14 (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!