Submission #1237391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237391		t_holl	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	2093 ms	21476 KiB

Main

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

const int INF = 5e17;

struct Road {
    int a, b, cost;

    int next (int u) {
        return u == a ? b : a;
    }
};

vector<Road> road_list;
vector<vector<int>> roads;

int N;

vector<int> dijkstra (int start) {
    priority_queue<pair<int, int>> queue;
    vector<int> distances(N, INF);

    distances[start] = 0;
    queue.push({ 0, start });

    while (queue.size() != 0) {
        pair<int, int> u = queue.top();
        queue.pop();

        int curr = u.second;
        int dist = - u.first;
        if (distances[curr] != dist) continue ;

        for (int r_id : roads[curr]) {
            int next = road_list[r_id].next(curr);
            int cost = dist + road_list[r_id].cost;

            if (distances[next] <= cost) continue ;

            distances[next] = cost;
            queue.push({ - cost, next });
        }
    }

    return distances;
}

void solve () {
    cin >> N;
    int M; cin >> M;

    int s, t, l, k;
    cin >> s >> t >> l >> k;
    s --; t --;

    roads.resize(N);
    for (int i = 0; i < M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a --,
        b --;

        road_list.push_back({ a, b, c });

        roads[a].push_back(i);
        roads[b].push_back(i);
    }

    int count = 0;

    vector<int> d_s = dijkstra(s);
    vector<int> d_t = dijkstra(t);

    if (d_s[t] <= k) {
        count = (N * (N - 1)) >> 1;
        cout << count << "\n";
        return ;
    }

    for (int a = 0; a < N; a ++) {
        for (int b = a + 1; b < N; b ++) {
            int dAB = d_s[a] + l + d_t[b];
            int dBA = d_s[b] + l + d_t[a];

            if (min(dAB, dBA) <= k)
                count ++;
        }
    }

    cout << count << "\n";
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

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