Submission #1293908

#TimeUsernameProblemLanguageResultExecution timeMemory
1293908nguyenkhangninh99Construction Project 2 (JOI24_ho_t2)C++20
100 / 100
148 ms24908 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 2e5 + 5;

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

vector<int> dijkstra(int source, int n){
    vector<int> dist(n + 1, 1e18);
    dist[source] = 0;

    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    pq.push({0, source});

    while(pq.size()){
        auto [d, u] = pq.top();
        pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w]: g[u]){
            if(dist[v] > d + w){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m, s, t, l, 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].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> dists = dijkstra(s, n);
    vector<int> distt = dijkstra(t, n);

    if(dists[t] <= k) cout << n * (n - 1) / 2;
    else{
        sort(dists.begin() + 1, dists.end());
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int c = k - (distt[i] + l);
            ans +=  upper_bound(dists.begin() + 1, dists.end(), c) - dists.begin() - 1;
        }
        cout << ans;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...