제출 #1180469

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

Main

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

typedef unsigned long long ll;

const int MAXN = 2000 * 1000;
vector<pair<int, ll>> graf[MAXN + 1];
ll odl[MAXN + 1];
priority_queue<pair<ll, int>> pq;
vector<ll> v1;
vector<ll> v2;
int n;

void djikstra(int start) {
    for (int i = 1; i <= n; i ++) {
        odl[i] = LLONG_MAX/100;
    }
    odl[start] = 0;
    pq.push({0, start});
    while (pq.size() > 0) {
        int v = pq.top().second;
        ll dist = pq.top().first;
        dist *= (-1);
        pq.pop();
        if (dist > odl[v]) {
            continue;
        }
        for (auto u : graf[v]) {
            if (odl[v] + u.second < odl[u.first]) {
                odl[u.first] = odl[v] + u.second;
                pq.push({-odl[u.first], u.first});
            }
        }
    }
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, s, t, a, b;
    ll c, k, w;
    cin >> n >> m >> s >> t >> c >> k;
    for (int i = 0; i < m; i ++) {
        cin >> a >> b >> w;
        graf[a].push_back({b, w});
        graf[b].push_back({a, w});
    }

    djikstra(s);
    for (int i = 1; i <= n ; i ++) {
        v1.push_back(odl[i]);
    }
    if (odl[t] <= k) {
        cout << (ll(n) * ll(n - 1))/ 2 << "\n";
        return 0;
    }

    djikstra(t);
    for (int i = 1; i <= n ; i ++) {
        v2.push_back(odl[i]);
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    int kon = n - 1;
    ll wyn = 0;
    for (int pocz = 0; pocz < n; pocz ++) {
        while (kon >= 0 && (v2[kon] + v1[pocz] + c > k)) {
            kon --;
        }
        wyn += ll(kon + 1);
    }
    cout << wyn << "\n";


    return 0;
}

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