Submission #1090641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090641		Octa_pe_info	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	558 ms	262144 KiB

commuter_pass

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;

struct arbore {
    long long nod, cost;
    bool operator>(arbore other) const {
        return cost > other.cost;
    }
};

struct arbore2 {
    long long nod, cost, stare;
};

long long n, m, u, v, s, t;
long long rez = 1e18;
vector<vector<arbore>> tabel;
vector<vector<long long>> drumuri;
vector<long long> d;

void dij(long long start) {
    priority_queue<arbore, vector<arbore>, greater<arbore>> pq;
    d[start] = 0;
    pq.push({start, 0});

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

        if (d[curent.nod] < curent.cost)
            continue;

        for (auto i : tabel[curent.nod]) {
            if (d[i.nod] > curent.cost + i.cost) {
                d[i.nod] = curent.cost + i.cost;
                pq.push({i.nod, d[i.nod]});
            }
        }
    }
}

void rec(long long start, long long sf) {
    queue<arbore2> q;
    long long mx = 0;

    drumuri[0].push_back(start);
    q.push({start, d[start], 0});

    while (!q.empty()) {
        arbore2 curent = q.front();
        q.pop();

        if (curent.nod == sf)
            continue;

        long long cnt = 0;

        for (auto i : tabel[curent.nod]) {
            if (d[i.nod] == curent.cost - i.cost) {
                if (cnt == 0) {
                    drumuri[curent.stare].push_back(i.nod);
                    q.push({i.nod, d[i.nod], curent.stare});
                    cnt++;
                    mx = max(mx, curent.stare);
                } else {
                    long long nou = mx + 1;
                    drumuri[nou] = drumuri[curent.stare];
                    drumuri[nou].push_back(i.nod);
                    cnt++;
                    q.push({i.nod, d[i.nod], nou});
                    mx = max(mx, nou);
                }
            }
        }
    }
}

void calc(vector<vector<arbore>>& tabel2) {
    priority_queue<arbore, vector<arbore>, greater<arbore>> pq;
    vector<long long> di(n + 1, 1e18);
    pq.push({u, 0});
    di[u] = 0;

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

        if (di[curent.nod] < curent.cost)
            continue;

        for (auto i : tabel2[curent.nod]) {
            if (di[i.nod] > curent.cost + i.cost) {
                di[i.nod] = curent.cost + i.cost;
                pq.push({i.nod, di[i.nod]});
            }
        }
    }

    rez = min(rez, di[v]);
}

int main() {
    cin >> n >> m >> s >> t >> u >> v;

    tabel.resize(n + 1);
    d.resize(n + 1, 1e18);
    drumuri.resize(n + 1);

    for (long long i = 1; i <= m; i++) {
        long long a, b, c;
        cin >> a >> b >> c;

        tabel[a].push_back({b, c});
        tabel[b].push_back({a, c});
    }

    // Step 1: Dijkstra from S to T
    dij(s);

    // Step 2: Reconstruct the shortest path
    rec(t, s);

    // Step 3: Calculate minimal cost from U to V
    for (long long i = 0; i < drumuri.size(); i++) {
        if (drumuri[i].size() == 0)
            break;

        vector<vector<arbore>> nou = tabel;

        // Mark the edges in the shortest path as 0 cost
        for (long long j = 0; j < drumuri[i].size() - 1; j++) {
            long long a = drumuri[i][j], b = drumuri[i][j + 1];
            for (auto& edge : nou[a]) {
                if (edge.nod == b)
                    edge.cost = 0;
            }
            for (auto& edge : nou[b]) {
                if (edge.nod == a)
                    edge.cost = 0;
            }
        }

        // Recalculate the minimal cost from U to V
        calc(nou);
    }

    cout << rez << endl;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:127:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (long long i = 0; i < drumuri.size(); i++) {
      |                           ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:134:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for (long long j = 0; j < drumuri[i].size() - 1; j++) {
      |                               ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45