Submission #1243127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243127		attky	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	227 ms	39844 KiB

commuter_pass

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

using namespace std;

struct Vertice {
    int start, end, cost;
};

struct compare {
    bool operator() (Vertice a, Vertice b) {
        return a.cost > b.cost;
    }
};

vector<Vertice> graph[100100];
vector<vector<Vertice>> minGraph(100100);
bool done[100100];
int costMin[100100], costMinA[100100], costMinB[100100], costMinCumul[100100], costMinCumul2[100100];

void cumulB(int pos) {
    done[pos] = true;
    costMinCumul[pos] = costMinB[pos];
    for(int loop = 0; loop < minGraph[pos].size(); ++loop) {
        if(!done[minGraph[pos][loop].end]) {
            cumulB(minGraph[pos][loop].end);
        }
        costMinCumul[pos] = min(costMinCumul[minGraph[pos][loop].end], costMinCumul[pos]);
    }
}

vector<vector<Vertice>> inverse() {
    vector<vector<Vertice>> inv(100100);
    for(int loop = 0; loop < 100100; ++loop) {
        for(int looping = 0; looping < minGraph[loop].size(); ++looping) {
            inv[minGraph[loop][looping].end].push_back({minGraph[loop][looping].end, loop, minGraph[loop][looping].cost});
        }
    }
    return inv;
}

void cumulB2(int pos) {
    costMinCumul2[pos] = costMinB[pos];
    for(int loop = 0; loop < minGraph[pos].size(); ++loop) {
        if(done[minGraph[pos][loop].end]) {
            if(costMinCumul2[minGraph[pos][loop].end] == 2e18) {
                cumulB2(minGraph[pos][loop].end);
            }
            costMinCumul2[pos] = min(costMinCumul2[pos], costMinCumul2[minGraph[pos][loop].end]);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nbVilles, nbRoutes, start, end, bookA, bookB;
    cin >> nbVilles >> nbRoutes >> start >> end >> bookA >> bookB;
    start--;end--;bookA--;bookB--;

    for(int loop = 0; loop < nbRoutes; ++loop) {
        int nodeA, nodeB, cost;
        cin >> nodeA >> nodeB >> cost;
        nodeA--;nodeB--;
        graph[nodeA].push_back({nodeA, nodeB, cost});
        graph[nodeB].push_back({nodeB, nodeA, cost});
    }

    priority_queue<Vertice, vector<Vertice>, compare> q;
    q.push({-1, start, 0});

    for(int loop = 0; loop < nbVilles; ++loop) {
        done[loop] = false;
        costMin[loop] = 2e18;
    }
    costMin[start] = 0;

    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(done[enCours.end]) {
            continue;
        }
        done[enCours.end] = true;
        
        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            Vertice arrivee = graph[enCours.end][loop];
            if(done[arrivee.end]) {
                continue;
            }
            if(costMin[arrivee.end] == arrivee.cost + enCours.cost) {
                minGraph[arrivee.end].push_back({arrivee.end, arrivee.start, 0});
            }
            else if(costMin[arrivee.end] > arrivee.cost + enCours.cost) {
                minGraph[arrivee.end].clear();
                minGraph[arrivee.end].push_back({arrivee.end, arrivee.start, 0});
                costMin[arrivee.end] = arrivee.cost + enCours.cost;
                q.push({arrivee.start, arrivee.end, costMin[arrivee.end]});
            }
        }
    }
    

    for(int loop = 0; loop < nbVilles; ++loop) {
        done[loop] = false;
        costMin[loop] = 2e18;
    }
    costMin[bookA] = 0;
    q.push({-1, bookA, 0});

    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(done[enCours.end]) {
            continue;
        }
        done[enCours.end] = true;

        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            Vertice arrivee = graph[enCours.end][loop];
            if(done[arrivee.end]) {
                continue;
            }
            if(costMin[arrivee.end] > enCours.cost + arrivee.cost) {
                costMin[arrivee.end] = enCours.cost + arrivee.cost;
                q.push({arrivee.start, arrivee.end, enCours.cost + arrivee.cost});
            }
        }
    }

    int mini = costMin[bookB];

    for(int loop = 0; loop < nbVilles; ++loop) {
        costMinA[loop] = 2e18;
        costMinB[loop] = 2e18;
        done[loop] = false;
    }
    costMinA[bookA] = 0;
    costMinB[bookB] = 0;
    q.push({-1, bookA, 0});

    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(done[enCours.end]) {
            continue;
        }
        done[enCours.end] = true;

        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            Vertice arrivee = graph[enCours.end][loop];
            if(done[arrivee.end]) {
                continue;
            }
            if(costMinA[arrivee.end] > enCours.cost + arrivee.cost) {
                costMinA[arrivee.end] = enCours.cost + arrivee.cost;
                q.push({arrivee.start, arrivee.end, enCours.cost + arrivee.cost});
            }
        }
    }

    for(int loop = 0; loop < nbVilles; ++loop) {
        done[loop] = false;
    }
    q.push({-1, bookB, 0});

    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(done[enCours.end]) {
            continue;
        }
        done[enCours.end] = true;

        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            Vertice arrivee = graph[enCours.end][loop];
            if(done[arrivee.end]) {
                continue;
            }
            if(costMinB[arrivee.end] > enCours.cost + arrivee.cost) {
                costMinB[arrivee.end] = enCours.cost + arrivee.cost;
                q.push({arrivee.start, arrivee.end, enCours.cost + arrivee.cost});
            }
        }
    }

    for(int loop = 0; loop < nbVilles; ++loop) {
        done[loop] = false;
    }

    for(int loop = 0; loop < nbVilles; ++loop) {
        costMinCumul[loop] = 2e18;
        costMinCumul2[loop] = 2e18;
    }

    cumulB(end);
    minGraph = inverse();
    cumulB2(start);

    for(int loop = 0; loop < nbVilles; ++loop) {
        if(done[loop]) {
            mini = min(mini, costMinA[loop] + min(costMinCumul[loop], costMinCumul2[loop]));
        }
    }
    cout << mini << '\n';
}

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