Submission #1155276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155276		KK_1729	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	157 ms	24904 KiB

Main

#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();
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47