Submission #1257212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257212		chautanphat	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	10 ms	11588 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;
vector<pair<int, int>> a[N];

vector<long long> dijkstra(int s)
{
    vector<long long> d(N, 1e16);
    priority_queue<pair<long long, int>> q;
    d[s] = 0;
    q.push({0, s});

    while (!q.empty())
    {
        long long w;
        int u;
        tie(w, u) = q.top();
        q.pop();
        if (d[u] != -w) continue;
        for (auto [v, w] : a[u])
        {
            if (d[u]+w < d[v])
            {
                d[v] = d[u]+w;
                q.push({-d[v], v});
            }
        }
    }

    return d;
}

int main()
{    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, s, t, l;
    long long k;
    cin >> n >> m >> s >> t >> l >> k;

    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    
    vector<long long> ds = dijkstra(s), dt = dijkstra(t), du = ds, dv = dt;
    sort(ds.begin()+1, ds.end());
    sort(dt.begin()+1, dt.end());

    long long ans = 0;
    for (int i = 1, j = n; i <= n; i++)
    {
        while (j > 0 && ds[i]+dt[j]+l > k) j--;
        ans += j;
    }
    if (du[t]+l<= k)
        for (int i = 1; i <= n; i++)
            if (du[i] + dv[i] == du[t]) ans--;
    cout << ans;

    return 0;
}

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