fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #define ull unsigned long long
  5. #define mod 1000000007
  6. #define pb push_back
  7. #define ll long long
  8. const int N =1e5+5;
  9. ll n,m,k;
  10. int d(ll w,vector<pair<pair<ll,ll>,ll>>adj[])
  11. {
  12.     priority_queue<pair<ll,ll>>pq;
  13.     vector<ll>dis(N,1e18);
  14.     pq.push({0,1});
  15.     dis[1]=0;
  16.     while(!pq.empty())
  17.     {
  18.         int node= pq.top().second;
  19.         int cost= -pq.top().first;
  20.         pq.pop();
  21.         if(dis[node]<cost) continue;
  22.         if(n==node) break;
  23.         for(auto i: adj[node])
  24.         {
  25.             if(i.second> w) continue;
  26.             ll d= i.first.second,ch= i.first.first;
  27.             if(dis[ch]>d+cost)
  28.             {
  29.                 dis[ch]=d+cost;
  30.                 pq.push({-dis[ch],ch});
  31.             }
  32.         }
  33.     }
  34.     return dis[n];
  35. }
  36. int main()
  37. {
  38.     ios::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.     int t;
  42.     cin >>t;
  43.     while(t--)
  44.     {
  45.         cin >> n >> m >>k;
  46.         vector<pair<pair<ll,ll>,ll>>adj[N];
  47.         for(int i=0;i<m;i++)
  48.         {
  49.             ll from,to,c,w;
  50.             cin >> from>>to>>c>>w;
  51.             adj[from].pb({{to,c},w});
  52.             adj[to].pb({{from,c},w});
  53.         }
  54.         if(n==1)
  55.         {
  56.             cout << 0 << endl;
  57.             continue;
  58.         }
  59.         if(m==0)
  60.         {
  61.             cout << -1 << endl;
  62.             continue;
  63.         }
  64.         ll r=1e10,l=1,anss=-1;
  65.         while(l<=r)
  66.         {
  67.             ll m= (l+r)/2;
  68.             ll ans = d(m,adj);
  69.             if(ans<k)
  70.             {
  71.                     anss=m;
  72.                     r=m-1;
  73.  
  74.             }
  75.             else
  76.             {
  77.                 l=m+1;
  78.             }
  79.  
  80.         }
  81.         cout << anss<< endl;
  82.     }
  83. }
  84.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BSBbH8
language:
C++14 (clang 8.0)
created:
12 days 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!