Submission #399846

#	Time	Username	Problem	Language	Result	Execution time	Memory
399846		fvogel499	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	509 ms	27312 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define siz 100000
#define inf 1e18
#define int long long

int distFromB [siz];
int distFromA [siz];
int distFromDest [siz][4];

struct cdfb { bool operator()(int a, int b) { return (distFromB[a] > distFromB[b]); } };

struct cdfa { bool operator()(int a, int b) { return (distFromA[a] > distFromA[b]); } };

struct cdfd { bool operator()(pii a, pii b) { return (distFromDest[a.first][a.second] > distFromDest[b.first][b.second]); } };

int32_t main() {
    int nbNodes, nbEdges;
    cin >> nbNodes >> nbEdges;
    int passA, passB;
    cin >> passA >> passB;
    passA--;
    passB--;
    int origin, destination;
    cin >> origin >> destination;
    origin--;
    destination--;

    vector<vector<pii>> graph(nbNodes);
    for (int i = 0; i < nbEdges; i++) {
        int la, lb, lw;
        cin >> la >> lb >> lw;
        la--;
        lb--;
        graph[la].push_back(pii(lb, lw));
        graph[lb].push_back(pii(la, lw));
    }

    bool proc [nbNodes];
    for (int i = 0; i < nbNodes; i++) {
        proc[i] = false;
        distFromB[i] = inf;
    }
    priority_queue<int, vector<int>, cdfb> pq1;
    distFromB[passB] = 0;
    pq1.push(passB);
    while (!pq1.empty()) {
        int cn = pq1.top();
        pq1.pop();
        if (proc[cn]) continue;
        proc[cn] = true;
        for (pii ne : graph[cn]) {
            int nn = ne.first;
            int nd = distFromB[cn]+ne.second;
            if (nd < distFromB[nn]) {
                distFromB[nn] = nd;
                pq1.push(nn);
            }
        }
    }

    for (int i = 0; i < nbNodes; i++) {
        proc[i] = false;
        distFromA[i] = inf;
    }
    priority_queue<int, vector<int>, cdfa> pq2;
    distFromA[passA] = 0;
    pq2.push(passA);
    while (!pq2.empty()) {
        int cn = pq2.top();
        pq2.pop();
        if (proc[cn]) continue;
        proc[cn] = true;
        for (pii ne : graph[cn]) {
            int nn = ne.first;
            int nd = distFromA[cn]+ne.second;
            if (nd < distFromA[nn]) {
                distFromA[nn] = nd;
                pq2.push(nn);
            }
        }
    }

    set<pii> stbEdges;
    for (int i = 0; i < nbNodes; i++) {
        for (pii j : graph[i]) {
            if (distFromB[i] < distFromB[j.first] and distFromB[i]+distFromA[j.first]+j.second == distFromB[passA]) {
                stbEdges.insert(pii(i, j.first));
            }
        }
    }

    bool procState [nbNodes][4];
    for (int i = 0; i < nbNodes; i++) for (int j = 0; j < 4; j++) {
        procState[i][j] = false;
        distFromDest[i][j] = inf;
    }
    priority_queue<pii, vector<pii>, cdfd> q;
    distFromDest[origin][0] = 0;
    q.push(pii(origin, 0));
    while (!q.empty()) {
        int cn = q.top().first;
        int cs = q.top().second;
        q.pop();
        if (procState[cn][cs]) continue;
        proc[cn] = true;
        if (cn == destination) {
            cout << distFromDest[cn][cs];
            return 0;
        }
        for (pii ne : graph[cn]) {
            int nn = ne.first;
            if (cs != 3 and cs != 2 and stbEdges.find(pii(cn, nn)) != stbEdges.end()) {
                int nd = distFromDest[cn][cs];
                int ns = 1;
                if (nd < distFromDest[nn][ns]) {
                    distFromDest[nn][ns] = nd;
                    q.push(pii(nn, ns));
                }
            }
            else if (cs != 3 and cs != 1 and stbEdges.find(pii(nn, cn)) != stbEdges.end()) {
                int nd = distFromDest[cn][cs];
                int ns = 2;
                if (nd < distFromDest[nn][ns]) {
                    distFromDest[nn][ns] = nd;
                    q.push(pii(nn, ns));
                }
            }
            int nd = distFromDest[cn][cs]+ne.second;
            int ns = 0;
            if (cs != 0) ns = 3;
            if (nd < distFromDest[nn][ns]) {
                distFromDest[nn][ns] = nd;
                q.push(pii(nn, ns));
            }
        }
    }

    int d = 0;
    d++;
}

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