Submission #1315657

#TimeUsernameProblemLanguageResultExecution timeMemory
1315657samarthkulkarniConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
157 ms24916 KiB
// joi final round 2024
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int N = 2e5+10;
vector<pr> adj[N];
ll n, m;

void dij(int a, vi &dist) {
	dist.resize(n+1, 2e15);
	dist[0] = 0;
	vector<bool> vis(n+1);

	priority_queue<pr> q;
	dist[a] = 0;
	q.push({0, a});

	while (!q.empty()) {
		auto [d, u] = q.top(); q.pop();
		if (vis[u]) continue;
		vis[u] = true;

		for (auto [v, w] : adj[u]) {
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				q.push({-dist[v], v});
			}
		}
	}
}


void solution() {
	cin >> n >> m;
	ll S, T, l, k;
	cin >> S >> T >> l >> k;

	while (m--) {
		ll a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}


	vi d1, d2;
	dij(S, d1);
	dij(T, d2);

	if (d1[T] <= k) {
		cout << n*(n-1)/2 << endl; 
		return;
	}


	ll ans = 0;


	sort(all(d1));
	sort(all(d2));


	
	int j = n;
	for (int i = 1; i <= n; i++) {
		while (j >= 1 && d2[j] > k-l-d1[i]) j--;
		ans += j;
	}

	// j = n;
	// for (int i = 1; i <= n; i++) {
	// 	while (j >= 1 && d1[j] > k-l-d2[i]) j--;
	// 	ans+=j;
	// }

	cout << ans << endl;



}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...