Submission #1124582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124582		LucaIlie	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	804 ms	45052 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, c;

    int other( int w ) {
        return u ^ v ^ w;
    }
};

struct elemPQ {
    int u;
    long long d;

    bool operator < ( const elemPQ &x ) const {
        return x.d < d;
    }
};

struct distancee {
    long long d1, d2;

    bool operator < ( const distancee &x ) const {
        if ( d1 == x.d1 )
            return d2 < x.d2;
        return d1 < x.d1;
    }
};

struct elemPQ2 {
    int u;
    distancee d;

    bool operator < ( const elemPQ2 &x ) const {
        return x.d < d;
    }
};

const int MAX_N = 1e5;
const int MAX_M = 2e5;
const long long INF = 1e18;
int n;
bool vis[4 * MAX_N + 1];
distancee minDist[4 * MAX_N + 1];
long long distX[MAX_N + 1], distY[MAX_N + 1];
vector<int> adj[MAX_N + 1];
edge edges[MAX_M];

void calcDist( int s, long long dist[] ) {
    priority_queue<elemPQ> pq;

    for ( int v = 1; v <= n; v++ ) {
        dist[v] = INF;
        vis[v] = false;
    }
    dist[s] = 0;
    pq.push( { s,dist[s] } );
    while ( !pq.empty() ) {
        int u = pq.top().u;
        pq.pop();

        if ( vis[u] )
            continue;
        vis[u] = true;

        for ( int e: adj[u] ) {
            int v = edges[e].other( u ), c = edges[e].c;
            if ( dist[u] + c < dist[v] ) {
                dist[v] = dist[u] + c;
                pq.push( { v, dist[v] } );
            }
        }
    }
}

int main() {
    int m, s, t, x, y;

    cin >> n >> m >> s >> t >> x >> y;
    for ( int e = 0; e < m; e++ ) {
        cin >> edges[e].u >> edges[e].v >> edges[e].c;
        adj[edges[e].u].push_back( e );
        adj[edges[e].v].push_back( e );
    }

    calcDist( x, distX );
    calcDist( y, distY );

    for ( int v = 1; v <= 4 * n; v++ ) {
        vis[v] = false;
        minDist[v] = { INF, INF };
    }

    priority_queue<elemPQ2> pq;
    minDist[s] = { 0, 0 };
    minDist[n + s] = { 0, distX[s] };
    minDist[2 * n + s] = { 0, distY[s] };
    minDist[3 * n + s] = { 0, distX[s] + distY[s] };
    pq.push( { s, minDist[s] } );
    pq.push( { n + s, minDist[n + s] } );
    pq.push( { 2 * n + s, minDist[2 * n + s] } );
    pq.push( { 3 * n + s, minDist[3 * n + s] } );
    while ( !pq.empty() ) {
        int u = pq.top().u;
        int p = (u - 1) / n;
        u = (u - 1) % n + 1;
        pq.pop();

        if ( vis[p * n + u] )
            continue;
        vis[p * n + u] = true;

        //printf( "%d %d %lld %lld\n", p, u, minDist[p * n + u].d1, minDist[p * n + u].d2 );
        for ( int e: adj[u] ) {
            int v = edges[e].other( u ), c = edges[e].c;
            for ( int q = 0; q < 4; q++ ) {
                if ( (p & q) != p )
                    continue;
                distancee newDist = minDist[p * n + u];;
                newDist.d1 += c;
                if ( (p ^ q) & 1 )
                    newDist.d2 += distX[v];
                if ( (p ^ q) & 2 )
                    newDist.d2 += distY[v];
                if ( newDist < minDist[q * n + v] ) {
                    minDist[q * n + v] = newDist;
                    pq.push( { q * n + v, minDist[q * n + v] } );
                }
            }
        }
    }

    cout << min( distX[y], minDist[3 * n + t].d2 ) << "\n";
}

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