제출 #1199828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199828		zsombor	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	242 ms	28664 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

ll n, m, s, t, l, k, p, ans;
vector <vector <pair <int, ll>>> g(3e5);
vector <ll> d1(3e5, 1e18);
vector <ll> d2(3e5, 1e18);
vector <ll> e;
vector <ll> f;

void dijkstra(int x, vector <ll>& d) {
	priority_queue <pair <ll, int>> q;
	vector <bool> done(3e5, false);
	d[x] = 0;
	q.push({ 0,x });
	while (q.size()) {
		int a = q.top().second;
		q.pop();
		if (done[a]) continue;
		done[a] = true;
		for (auto p : g[a]) {
			ll b = p.first, c = p.second;
			if (d[a] + c < d[b]) {
				d[b] = d[a] + c;
				q.push({ -d[b],b });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> s >> t >> l >> k;
	ll a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		g[a].push_back({ b,c });
		g[b].push_back({ a,c });
	}
	dijkstra(s, d1);
	dijkstra(t, d2);
	if (d1[t] <= k) { cout << n * (n - 1) / 2; return 0; }
	e.resize(n);
	f.resize(n);
	for (int i = 0; i < n; i++) {
		e[i] = d1[i + 1];
		f[i] = d2[i + 1];
	}
	sort(e.begin(), e.end());
	sort(f.begin(), f.end());
	p = n - 1;
	for (int i = 0; i < n; i++) {
		while (p >= 0 && e[i] + f[p] + l > k) p--;
		ans += p + 1;
	}
	cout << ans;
}

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