#include <bits/stdc++.h>
using namespace std;
/*
Ben Watson
Handle codeforces : quangminh98
Mua Code nhu mua Florentino !!
*/
#define ll long long
const string name = "test";
void solve();
signed main()
{
if (fopen((name + ".inp").c_str(), "r"))
{
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
// main program
const int maxn = 2e5 + 1;
const ll oo = 0x3f3f3f3f3f3f3f3f;
vector<pair<int, int>> adj[maxn];
int n, m, s, t, l;
ll k;
vector<ll> Dijkstra(int source)
{
vector<ll> dist(n + 1, oo);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({dist[source] = 0, source});
while (!pq.empty())
{
int u = pq.top().second;
ll w = pq.top().first;
pq.pop();
if (dist[u] != w)
continue;
for (pair<int, int> nxt : adj[u])
{
int v = nxt.first, w = nxt.second;
if (dist[v] > dist[u] + w)
pq.push({dist[v] = dist[u] + w, v});
}
}
return dist;
}
void solve()
{
cin >> n >> m >> s >> t >> l >> k;
for (int i = 0; i < m; i++)
{
int u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
vector<ll> S = Dijkstra(s), T = Dijkstra(t);
if (S[t] <= k)
{
cout << 1ll * n * (n - 1) / 2 << '\n';
return;
}
sort(S.begin() + 1, S.end());
sort(T.begin() + 1, T.end());
ll res = 0;
for (int i = 1; i <= n; i++)
{
int pos = upper_bound(T.begin() + 1, T.end(), k - l - S[i]) - T.begin();
res += pos - 1;
}
cout << res << '\n';
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((name + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |