#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(const T &v, int lim = 1e9)
{
for(auto x : v)
if(lim-- > 0) cout << x << " ";
cout << "\n";
}
#define int long long
int N, M, S, T, L, K;
using node = pair<ll, ll>;
vector<node> adj[200005];
signed main()
{
ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M >> S >> T >> L >> K;
for(int i = 0; i < M; i++)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
auto dij = [&](int start)
{
priority_queue<node, vector<node> , greater<node>> q;
vector<ll> d(N + 5, 1e17);
d[start] = 0;
q.emplace(0, start);
while(!q.empty())
{
auto [c, v] = q.top(); q.pop();
if(c != d[v]) continue;
for(auto [u, w] : adj[v])
{
if(c + w < d[u])
{
d[u] = c + w;
q.emplace(c + w, u);
}
}
}
return d;
};
auto ds = dij(S);
auto dt = dij(T);
// print(ds);
// print(dt);
ll cnt = 0;
for(int i = 1; i <= N; i++)
{
for(int j = i + 1; j <= N; j++)
{
ll cost = min(ds[i] + dt[j], ds[j] + dt[i]) + L;
if(cost <= K)
{
cnt++;
// cout << cost << endl;
// cout << i << " ," << j << endl;
}
}
}
if(ds[T] <= K) cnt = N * (N - 1) / 2;
cout << cnt << "\n";
}
# | 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... |