제출 #1327524

#제출 시각아이디문제언어결과실행 시간메모리
1327524proshel_afgan_2015Construction Project 2 (JOI24_ho_t2)C++20
100 / 100
368 ms31744 KiB
#include <bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pi pair<int, int>
#define f first
#define s second

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int s, t, l, k;
    cin >> s >> t >> l >> k;
    --s, --t;
    vector<vector<pi>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> dist(n, 1e18), was(n);
    set<pi> st;
    dist[s] = 0;
    st.insert({dist[s], s});
    while (!st.empty()) {
        int u = st.begin()->s;
        st.erase(st.begin());
        was[u] = 1;
        for (auto& [v, w] : g[u]) {
            if (was[v]) continue;
            st.erase({dist[v], v});
            dist[v] = min(dist[v], dist[u] + w);
            st.insert({dist[v], v});
        }
    }
    if (dist[t] <= k) {
        cout << n * (n - 1) / 2 << "\n";
        return 0;
    }

    vector<int> dist2(n, 1e18);
    was.assign(n, 0);
    dist2[t] = 0;
    st.insert({dist2[t], t});
    while (!st.empty()) {
        int u = st.begin()->s;
        st.erase(st.begin());
        was[u] = 1;
        for (auto& [v, w] : g[u]) {
            if (was[v]) continue;
            st.erase({dist2[v], v});
            dist2[v] = min(dist2[v], dist2[u] + w);
            st.insert({dist2[v], v});
        }
    }
    sort(all(dist));
    sort(all(dist2));
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int w = dist2[i];
        if (w + l > k) break;
        int mx = k - l - w;
        res += lower_bound(all(dist), mx + 1) - dist.begin();
    }
    cout << res << "\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...