Submission #1095703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095703		zaza	Construction Project 2 (JOI24_ho_t2)	C++14	100 / 100	158 ms	27836 KiB

Main

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> g[200005];

long long d[2][200005];

void dij(int i, int s) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
	q.emplace(0, s);
	d[i][s] = 0;
	while (q.size()) {
		int u = q.top().second;
		long long dl = q.top().first;
		q.pop();
		if (dl > d[i][u]) {
			continue;
		}
		for (pair<int, int> p: g[u]) {
			int v = p.first, w = p.second;
			if (d[i][v] > d[i][u] + w) {
				d[i][v] = d[i][u] + w;
				q.emplace(d[i][v], v);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, s, t, l;
	long long k;
	
	cin >> n >> m >> s >> t >> l >> k;
		
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}

	memset(d, 0x3f3f3f3f, sizeof d);
	
	dij(0, s);
	dij(1, t);
	
	if (d[0][t] <= k) {
		cout << 1ll * n * (n - 1) / 2 << '\n';
		return 0;
	}
	
	vector<long long> v;
	
	for (int i = 1; i <= n; ++i) {
		v.emplace_back(d[1][i]);
	}
	
	sort(v.begin(), v.end());
	
	long long ans = 0;
	
	for (int i = 1; i <= n; ++i) {
		int j = upper_bound(v.begin(), v.end(), k - l - d[0][i]) - v.begin();
		if (d[1][i] <= k - l - d[0][i]) {
			j--;
		}
		ans += j;
	}
	
	cout << ans << '\n';
	
}
/*
18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645
*/

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