Submission #1155276

#TimeUsernameProblemLanguageResultExecution timeMemory
1155276KK_1729Construction Project 2 (JOI24_ho_t2)C++17
100 / 100
157 ms24904 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"


void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
vector<vector<pair<int, int>>> graph;
vector<int> dijkstra(int x, int n){
	vector<int> dist(n+1, 1e16);
	dist[0] = 1e17;
	using T = pair<long long, int>;
	
	priority_queue<T, vector<T>, greater<T>> pq;

	dist[x] = 0;
	pq.push({0, x});

	while (!pq.empty()){
		auto [cdist, node] = pq.top();
		pq.pop();

		if (cdist != dist[node]) continue;

		for (auto [item, d]: graph[node]){
			if (cdist+d < dist[item]){
				pq.push({dist[item] = cdist+d, item});
			}
		}
	}
	return dist;

}
void solve(){
	int n, m; cin >> n >> m;
	int s, t, l, k; cin >> s >> t >> l >> k;
	graph.resize(n+1);
	FOR(i,0,m){
		int a, b, c; cin >> a >> b >> c;
		graph[a].pb({b, c});
		graph[b].pb({a, c});
	}

	vector<int> from_s = dijkstra(s, n);
	vector<int> from_t = dijkstra(t, n);

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

	sort(all(from_s));
	sort(all(from_t));

	int ans = 0;
	FOR(i,0,n){
		auto o = upper_bound(all(from_t), k-from_s[i]-l);
		if (o == from_s.begin()) continue;
		o--;
		int ind = o-from_t.begin();
		ans += ind+1;
	}

	cout << ans << endl;



}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...