Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct Edge
- {
- int f, s, t;
- };
- int main() {
- int n, m; cin >> n >> m;
- vector <Edge> v[n+1];
- bool visited[n+1]={false};
- ll distance[n+1];
- for (int i=1; i<=n; i++)
- distance[i]=pow(10,12);
- for (int i=1; i<=m; i++)
- {
- int x, y, z; cin >> x >> y >> z;
- v[x].push_back({y,z,i});
- v[y].push_back({x,z,i});
- }
- int x, y; ll c; cin >> x >> y >> c;
- distance[x]=0;
- int l=1, r=m, mid;
- while (l<r)
- {
- mid=(l+r)/2; //cout << l << " " << mid << " " << r << endl;
- priority_queue <pair<ll,int> > q; q.push({0,x});
- while (!q.empty())
- {
- int a=q.top().second; q.pop();
- if (visited[a])
- {
- //cout << "hi" << endl;
- continue;
- }
- visited[a]=true;
- for (int u=0; u<v[a].size(); u++)
- {
- int b=v[a][u].f, w=v[a][u].s;
- //cout << a << " " << b << " " << v[a][u].t << " " << mid << endl << endl;
- if (v[a][u].t>mid) continue;
- if (distance[a]+w<distance[b])
- {
- distance[b]=distance[a]+w;
- q.push({-distance[b],b});
- }
- }
- }
- if (distance[y]<=c)
- {
- r=mid;
- for (int i=1; i<=n; i++)
- {
- distance[i]=pow(10,12);
- visited[i]=false;
- }
- distance[x]=0;
- }
- else if (distance[y]>c)
- {
- l=mid+1;
- //cout << l << " " << mid << " " << r << endl;
- if (l==m)
- {
- r++;
- }
- if (mid==m)
- {
- cout << -1;
- return 0;
- }
- for (int i=1; i<=n; i++)
- {
- distance[i]=pow(10,12);
- visited[i]=false;
- }
- distance[x]=0;
- }
- }
- cout << r;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement