This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
void testcase(){
int N, M, S, T, L; long long K;
cin >> N >> M >> S >> T >> L >> K;
--S, --T;
vector<vector<pair<int, int>>> adj(N);
while(M--){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
auto dijkstra = [&](int s){
vector<long long> d(N, inf);
d[s] = 0;
using node = pair<long long, int>;
priority_queue<node, vector<node>, greater<node>> pq;
pq.push({d[s], s});
while(!pq.empty()){
long long cur; int u;
tie(cur, u) = pq.top(); pq.pop();
for(auto [v, w] : adj[u]){
if(d[v] > d[u] + w){
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
return d;
};
vector<long long> dS = dijkstra(S), dT = dijkstra(T);
if(dS[T] <= K){
cout << 1LL * N * (N - 1) / 2;
return;
}
int cnt = 0;
for(int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
long long cur = min(dS[i] + dT[j], dS[j] + dT[i]) + L;
if(cur <= K) ++cnt;
}
}
cout << cnt << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while(T--) testcase();
return 0;
}
Compilation message (stderr)
Main.cpp: In lambda function:
Main.cpp:32:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for(auto [v, w] : adj[u]){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |