Submission #1035737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035737		borisAngelov	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	169 ms	65844 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000005;
const long long inf = (1LL << 61);

int n, m, s, t;
long long L, K;

long long ds[maxn], dt[maxn];
pair<long long, long long> d[maxn];

vector<pair<int, int>> g[maxn];

void dijkstra(int start, long long dist[])
{
    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, int>> pq;
    pq.push({0, start});
    dist[start] = 0;

    bool visited[n + 1] = {};

    while (!pq.empty())
    {
        auto top = pq.top();
        pq.pop();

        int node = top.second;
        long long curr = -top.first;

        if (visited[node] == true) continue;
        visited[node] = true;

        for (int i = 0; i < g[node].size(); ++i)
        {
            if (dist[g[node][i].first] > curr + g[node][i].second)
            {
                dist[g[node][i].first] = curr + g[node][i].second;
                pq.push({-dist[g[node][i].first], g[node][i].first});
            }
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m >> s >> t >> L >> K;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    dijkstra(s, ds);
    dijkstra(t, dt);

    if (ds[t] <= K)
    {
        cout << ((1LL * n) * (1LL * (n - 1))) / 2 << endl;
        return 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        d[i] = {ds[i], dt[i]};
    }

    sort(d + 1, d + n + 1);

    long long ans = 0;

    for (int i = 2; i <= n; ++i)
    {
        if (d[i].second == inf) continue;

        int l = 1;
        int r = i - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (d[i].second + d[mid].first <= K - L)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        ans += r;
    }

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dijkstra(int, long long int*)':
Main.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~

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