SHARE
TWEET

Untitled

a guest Sep 20th, 2019 98 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. struct Edge
  8. {
  9.     int f, s, t;
  10. };
  11.  
  12. int main() {
  13.     int n, m; cin >> n >> m;
  14.    
  15.     vector <Edge> v[n+1];
  16.     bool visited[n+1]={false};
  17.     ll distance[n+1];
  18.    
  19.     for (int i=1; i<=n; i++)
  20.     distance[i]=pow(10,12);
  21.    
  22.     for (int i=1; i<=m; i++)
  23.     {
  24.         int x, y, z; cin >> x >> y >> z;
  25.         v[x].push_back({y,z,i});
  26.         v[y].push_back({x,z,i});
  27.     }
  28.    
  29.     int x, y; ll c; cin >> x >> y >> c;
  30.     distance[x]=0;
  31.    
  32.     int l=1, r=m, mid;
  33.    
  34.     while (l<r)
  35.     {
  36.         mid=(l+r)/2; //cout << l << " " << mid << " " << r << endl;
  37.        
  38.         priority_queue <pair<ll,int> > q; q.push({0,x});
  39.         while (!q.empty())
  40.         {
  41.             int a=q.top().second; q.pop();
  42.             if (visited[a])
  43.             {
  44.                 //cout << "hi" << endl;
  45.                 continue;
  46.             }
  47.             visited[a]=true;
  48.            
  49.             for (int u=0; u<v[a].size(); u++)
  50.             {
  51.                 int b=v[a][u].f, w=v[a][u].s;
  52.                
  53.                 //cout << a << " " << b << "  " << v[a][u].t << " " << mid << endl << endl;
  54.                
  55.                 if (v[a][u].t>mid) continue;
  56.                
  57.                 if (distance[a]+w<distance[b])
  58.                 {
  59.                     distance[b]=distance[a]+w;
  60.                     q.push({-distance[b],b});
  61.                 }
  62.             }
  63.         }
  64.        
  65.         if (distance[y]<=c)
  66.         {
  67.             r=mid;
  68.            
  69.             for (int i=1; i<=n; i++)
  70.             {
  71.                 distance[i]=pow(10,12);
  72.                 visited[i]=false;
  73.             }
  74.             distance[x]=0;
  75.         }
  76.        
  77.         else if (distance[y]>c)
  78.         {
  79.             l=mid+1;
  80.            
  81.             //cout << l << " " << mid << " " << r << endl;
  82.            
  83.             if (l==m)
  84.             {
  85.                 r++;
  86.             }
  87.            
  88.             if (mid==m)
  89.             {
  90.                 cout << -1;
  91.                 return 0;
  92.             }
  93.            
  94.             for (int i=1; i<=n; i++)
  95.             {
  96.                 distance[i]=pow(10,12);
  97.                 visited[i]=false;
  98.             }
  99.             distance[x]=0;
  100.         }
  101.     }
  102.    
  103.     cout << r;
  104. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top