제출 #1284142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284142		hamase	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	168 ms	26468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define bismillah ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define endl '\n'

ll inf = 4e18;
ll N, M, S, T, L, K;
vector<pll> adj[200005];

void dijkstra(int source, vector<ll>& dist) {
    vector<ll> vist(N+1);
    for (int i = 1; i <= N; i++) {
        dist[i] = inf;
        vist[i] = false;
    }
    dist[source] = 0;

    priority_queue<pll, vector<pll>, greater<pll>> pq;

    pq.push({0, source});

    while (!pq.empty()) {
        ll top = pq.top().se;
        pq.pop();
        if (vist[top]) continue;
        vist[top] = true;
        for (auto [nei, wei] : adj[top]) {
            if (dist[nei] > dist[top] + wei) {
                dist[nei] = dist[top] + wei;
                pq.push({dist[nei], nei});
            }
        }
    }
}

void solve() {
    cin >> N >> M >> S >> T >> L >> K;
    for (int i = 0; i < M; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    vector<ll> dariS(N+1), dariT(N+1);
    dijkstra(S, dariS);
    dijkstra(T, dariT);


    if (dariS[T] <= K) {
        cout << N*(N-1)/2 << endl;
        return;
    }

    vector<pll> no;
    for (int i = 1; i <= N; i++) {
        no.pb({dariT[i], i});
    }
    sort(no.begin(), no.end(), greater<pll>());

    ll ans = 0;
    for (int i = 0; i < N-1; i++) {
        int l = i+1;
        int r = N-1;
        int mid;
        int lb = -1;
        while (l <= r) {
            mid = (l + r)/2;

            if (dariS[no[i].se] + L + no[mid].fi <= K) {
                lb = mid;
                r = mid-1;
            } else l = mid+1;
        }
        if (lb != -1) {
            ans += (N-lb);
        }
    }
    cout << ans << endl;
}

int main() {
    bismillah;

    int T = 1;
    // cin >> T;

    for (;T--;) solve();
}

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