Submission #1136770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136770		Unforgettablepl	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	219 ms	24880 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,s,t,l,k;
    cin >> n >> m >> s >> t >> l >> k;
    vector<vector<pair<int,int>>> adj(n+1);
    for(int i=1;i<=m;i++) {
        int a,b,c;cin>>a>>b>>c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    auto dijkastra = [&](int x,vector<int> &ans) {
        priority_queue<pair<int,int>> pq;
        pq.emplace(0,x);
        vector<bool> visited(n+1);
        while(!pq.empty()) {
            auto [dist,curr] = pq.top();pq.pop();dist=-dist;
            if(visited[curr])continue;
            visited[curr]=true;
            ans[curr]=dist;
            for(auto&[x,c]:adj[curr])if(!visited[x])pq.emplace(-dist-c,x);
        }
    };
    vector<int> distFromS(n+1,1e16);
    dijkastra(s,distFromS);
    vector<int> distFromT(n+1,1e16);
    dijkastra(t,distFromT);
    if(distFromS[t]<=k) {
        cout << n*(n-1)/2 << '\n';
        return 0;
    }
    distFromT.erase(distFromT.begin());
    sort(distFromT.begin(), distFromT.end());
    int ans = 0;
    for(int i=1;i<=n;i++) {
        int allowed = k-distFromS[i]-l;
        ans+=upper_bound(distFromT.begin(), distFromT.end(), allowed)-distFromT.begin();
    }
    cout << ans << '\n';
}

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