Submission #1187478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187478		Quentolosse	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2096 ms	37780 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 1e18;

struct Arrete {
    int debut, fin, cout;
    bool sur_st = false;
};

vector<Arrete> arretes;
vector<vector<int>> stations;

int add_a(int a, int b, int c) {
    arretes.push_back({a, b, c});
    return arretes.size() - 1;
}

struct Pos {
    int pos, etat;

    bool operator<(const Pos& other) const {
        return pos < other.pos;
    }
};


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;

    int s, t, u, v;
    cin >> s >> t >> u >> v;
    s--;t--;u--;v--;

    stations.resize(n);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;

        a--; b--;
        int num = add_a(a, b, c);
        
        stations[a].push_back(num);
        stations[b].push_back(num);
    }

    priority_queue<pair<int,int>> pq;
    
    vector<int> profondeurs(n, INF);
    pq.push({0, s});

    while(!pq.empty()) {

        int prof = -pq.top().first;
        int pos = pq.top().second;
        pq.pop();

        if (profondeurs[pos] != INF) {
            if (pos == t) break;
            continue;
        }

        profondeurs[pos] = prof;

        for (auto &&i: stations[pos]) {
            pq.push(make_pair(- (arretes[i].cout + prof), arretes[i].debut + arretes[i].fin - pos));
        }
    }

    vector<int> positions;
    positions.push_back(t);

    while (!positions.empty())
    {
        int pos = positions.back();
        positions.pop_back();
        for (auto &&i: stations[pos]) {
            int dest = arretes[i].debut + arretes[i].fin - pos;
            if (profondeurs[dest] == profondeurs[pos] - arretes[i].cout) {
                arretes[i].sur_st = true;
                arretes[i].debut = dest;
                arretes[i].fin = pos;
                positions.push_back(dest);
            }
        }
    }

    priority_queue<pair<int, Pos>> file;
    vector<vector<bool>> vus(4, vector<bool> (n, false));


    file.push(make_pair(0, (Pos){u, 0}));
    while (!file.empty())
    {
        int prof = -file.top().first;
        Pos pos = file.top().second;

        file.pop();

        if (vus[pos.etat][pos.pos]) {
            continue;
        }

        
        if (pos.pos == v) {
            cout << prof << endl;
            return 0;
        }

        vus[pos.etat][pos.pos] = true;
        
        for (auto &&i: stations[pos.pos]) {
            int e = pos.etat;
            int moins_prof = 0;
            if (arretes[i].sur_st) {
                if (pos.etat != 3) {
                    e = 2;
                    if (pos.pos == arretes[i].debut) {
                        e = 1;
                    }
                    if (pos.etat == 0 || pos.etat == e) {
                        moins_prof = arretes[i].cout;
                    }
                    else {
                        e = 3;
                    }
                }
            }
            else {
                e = 0;
                if (pos.etat != 0) {
                    e = 3;
                }
            }
            file.push(make_pair(-(prof + arretes[i].cout - moins_prof), (Pos){arretes[i].debut + arretes[i].fin - pos.pos, e}));
        }
    }
    
    cerr << "EUH...\n";

    return 0;

}

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