Submission #1364499

#TimeUsernameProblemLanguageResultExecution timeMemory
1364499clemmy14Construction Project 2 (JOI24_ho_t2)C++20
100 / 100
316 ms31176 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int INF=1e18;

int n;
vector<vector<pair<int, int>>> adj;

vector<int> dijk(int st) {
    vector<bool> vis(n+1, false);
    vector<int> dis(n+1, INF); dis[st]=0;
    priority_queue<pair<int, int>> q; q.push({0, st});

    while(!q.empty()) {
        int node=q.top().second; q.pop();
        if(vis[node]) continue;
        vis[node]=true;
        for(auto [child, w] : adj[node]) {
            if(dis[child] > dis[node]+w) {
                dis[child]=dis[node]+w;
                q.push({-dis[child], child});
            }
        }
    }
    return dis;
}

signed main() {
    int m, s, t, l, k; cin >> n >> m >> s >> t >> l >> k;
    adj=vector<vector<pair<int, int>>>(n+1);
    for(int i=0; i<m; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    vector<int> disS=dijk(s), disT=dijk(t);

    if(disS[t] <= k) {
        cout << n*(n-1)/2;
        return 0;
    }

    map<int, int> cum; 

    for(int i=1; i<=n; i++) {
        if(disT[i] == INF) continue;    
        cum[disT[i]]++;
    }
    
    int prev=0;
    for(auto x : cum) {
        cum[x.first]+=prev;
        prev=cum[x.first];
    }

    //for(auto x : cum) cout << x.first << ' ' << x.second << endl;

    int ans=0;
    for(int i=1; i<=n; i++) {
        int otherD=k-(disS[i]+l);
        if(otherD >= 0) {
            auto it = cum.upper_bound(otherD);
            it--;
            ans+=it->second;
            if(disT[i] <= otherD) ans--;
        }
    }
    cout << ans;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...