Submission #991210

#	Time	Username	Problem	Language	Result	Execution time	Memory
991210		model_code	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	307 ms	23764 KiB

Main

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

using P = pair<long long, int>;

struct edge{
    int to;
    long long cost;
};

constexpr long long inf = 1e18;

int main(){
    int n, m;
    cin >> n >> m;
    
    int s, t;
    long long l, k;
    cin >> s >> t >> l >> k;
    s--;
    t--;

    vector<vector<edge>> g(n);
    for(int i = 0; i < m; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--;
        b--;

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    priority_queue<P, vector<P>, greater<P>> que;
    vector<long long> dist_from_s(n, inf), dist_from_t(n, inf);

    dist_from_s[s] = 0;
    que.push({0, s});
    while(!que.empty()){
        auto [dist, now] = que.top();
        que.pop();

        if(dist_from_s[now] < dist){
            continue;
        }

        for(auto [nxt, c]: g[now]){
            if(dist_from_s[nxt] > dist + c){
                dist_from_s[nxt] = dist + c;
                que.push({dist + c, nxt});
            }
        }
    }

    dist_from_t[t] = 0;
    que.push({0, t});
    while(!que.empty()){
        auto [dist, now] = que.top();
        que.pop();

        if(dist_from_t[now] < dist){
            continue;
        }

        for(auto [nxt, c]: g[now]){
            if(dist_from_t[nxt] > dist + c){
                dist_from_t[nxt] = dist + c;
                que.push({dist + c, nxt});
            }
        }
    }

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

    long long ans = 0;
    sort(dist_from_t.begin(), dist_from_t.end());

    for(int u = 0; u < n; u++){
        long long ok = k - l - dist_from_s[u];
        ans += lower_bound(dist_from_t.begin(), dist_from_t.end(), ok + 1) - dist_from_t.begin();
    }

    cout << ans << endl;
}

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