Submission #1315530

#TimeUsernameProblemLanguageResultExecution timeMemory
1315530samarthkulkarniConstruction Project 2 (JOI24_ho_t2)C++20
45 / 100
2092 ms19004 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);
	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);


	ll ans = 0;

	for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        if (d1[i] + l + d2[j] <= k || d1[j] + l + d2[i] <= k || d1[T] <= k || d2[S] <= k) { 
            ans++;
        }
    }
}
	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...