Submission #1212480

#TimeUsernameProblemLanguageResultExecution timeMemory
1212480VMaksimoski008Construction Project 2 (JOI24_ho_t2)C++17
100 / 100
266 ms24880 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 2e5 + 5;

vector<pll> g[N];
ll D[N][2], n, m, ans = 0;

void shortest_path(int s, int i) {
    for(int j=1; j<=n; j++) D[j][i] = 1e18;
    priority_queue<pll, vector<pll>, greater<> > pq;
    pq.push({ D[s][i] = 0, s });

    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d != D[u][i]) continue;
        for(auto [v, w] : g[u])
            if(D[v][i] > d + w) pq.push({ D[v][i] = d + w, v });
    }
}

signed main() {
    cin >> n >> m;
    ll s, t, L, K; cin >> s >> t >> L >> K;

    while(m--) {
        ll a, b, c; cin >> a >> b >> c;
        g[a].push_back({ b, c });
        g[b].push_back({ a, c });
    }

    shortest_path(s, 0);
    shortest_path(t, 1);

    vector<array<ll, 2> > a;
    for(int i=1; i<=n; i++) a.push_back({ D[i][0], D[i][1] });
    sort(a.begin(), a.end());

    for(int i=0; i<n; i++) {
        int p = upper_bound(a.begin(), a.end(), array<ll, 2>{ K-L-a[i][1], (ll)2e18 }) - a.begin() - 1;
        ans += min(i, p+1);
    }
    cout << (D[t][0] <= K ? (ll)n * (n-1) / 2 : ans) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...