Submission #1366867

#TimeUsernameProblemLanguageResultExecution timeMemory
1366867kawhietConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
2 ms580 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

#define int long long

constexpr int N = 2e5;
constexpr int inf = 1e18;

vector<array<int, 2>> g[N];

vector<int> get(int t, int n) {
    vector<int> dp(n, inf);
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> q;
    dp[t] = 0;
    q.push({0, t});
    while (!q.empty()) {
        auto [k, u] = q.top();
        q.pop();
        if (dp[u] < k) continue;
        for (auto [v, w] : g[u]) {
            if (k + w < dp[v]) {
                dp[v] = k + w;
                q.push({dp[v], v});
            }
        }
    }
    return dp;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t, l, k;
    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--; y--;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    s--; t--;
    vector<int> d1 = get(s, n);
    vector<int> d2 = get(t, n);
    sort(d2.begin(), d2.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x = k - d1[i] - l;
        ans += upper_bound(d2.begin(), d2.end(), x) - d2.begin();
    }
    cout << ans << '\n';
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...