#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int INF = 1LL<<61;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
signed main() {
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
freopen("output.txt", "w", stdout);
#endif
/*#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#endif*/ //fast IO
int n,m; cin >> n >> m;
int S,T,L,K; cin >> S >> T >> L >> K; S--; T--;
vector<vector<pair<int,int>>> adjlist(n);
for (int i=0; i<m; i++) {
int u,v,w; cin >> u >> v >> w; u--; v--;
adjlist[u].push_back({v,w}); adjlist[v].push_back({u,w});
}
vector<int> distS(n,INF);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> vals;
distS[S] = 0;
for (int i=0; i<n; i++) {
vals.push({distS[i],i});
}
while (vals.size()) {
pair<int,int> fir = vals.top(); vals.pop();
int u = fir.second; int dis = fir.first;
if (dis>distS[u]) continue;
for (pair<int,int> j:adjlist[u]) {
if (dis+j.second<distS[j.first]) {
vals.push({dis+j.second,j.first});
distS[j.first] = dis+j.second;
}
}
}
vector<int> distT(n,INF);
distT[T] = 0;
for (int i=0; i<n; i++) {
vals.push({distT[i],i});
}
while (vals.size()) {
pair<int,int> fir = vals.top(); vals.pop();
int u = fir.second; int dis = fir.first;
if (dis>distT[u]) continue;
for (pair<int,int> j:adjlist[u]) {
if (dis+j.second<distT[j.first]) {
vals.push({dis+j.second,j.first});
distT[j.first] = dis+j.second;
}
}
}
if (distS[T]<=K) {
cout << n*(n-1)/2 << endl;
return 0;
}
vector<int> s_sorted;
for (int i=0; i<n; i++) {
s_sorted.push_back(i);
}
sort(s_sorted.begin(), s_sorted.end(), [&](const int i1, const int i2) {
return distS[i1]>distS[i2];
}); //descending order to ensure distS[v]>distS[u]
ordered_set distv;
int su = 0;
for (int i=0; i<n; i++) {
int u = s_sorted[i];
int max_poss_weight = K-L-distS[u];
su+=distv.order_of_key(max_poss_weight+1);
distv.insert(distT[u]);
}
cout << su << endl;
for (int i=0; i<n; i++) {
//cout << i <<" " << distS[i] << " " << distT[i] << endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
120 ms |
292072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
291924 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
291924 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
120 ms |
292072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
