Submission #1122824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122824		LucaIlie	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	508 ms	2136 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, c, d;
};

struct vd {
    int v, d;

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

const int MAX_N = 200;
const int MAX_M = 5e4;
const int INF = 1e9;
int n;
bool vis[MAX_N + 1], used1[MAX_M + 1], usedN[MAX_M + 1], usedNew[MAX_M + 1];
int dist[MAX_N + 1][MAX_N + 1], distNew[MAX_N + 1], parent[MAX_N + 1];
vector<int> adjIn[MAX_N + 1], adjOut[MAX_N + 1];
edge edges[MAX_M];

int specialEdge;
void getDistances( int s, int t, int dist[], bool used[] ) {
    for ( int v = 1; v <= n; v++ )
        dist[v] = INF, vis[v] = false;

    priority_queue<vd> pq;
    dist[s] = 0;
    pq.push( { s, dist[s] } );
    while ( !pq.empty() ) {
        int u = pq.top().v;
        pq.pop();

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

        for ( int e: adjOut[u] ) {
            int v = edges[e].v, c = edges[e].c;
            if ( e == specialEdge && v == u )
                continue;
            if ( dist[u] + c < dist[v] ) {
                dist[v] = dist[u] + c;
                parent[v] = e;
                pq.push( { v, dist[v] } );
            }
        }
    }

    if ( dist[t] != INF ) {
        int v = t;
        while ( v != s ) {
            int e = parent[v];
            used[e] = true;
            v = edges[e].u;
        }
    }
}

int main() {
    int m;

    cin >> n >> m;
    for ( int e = 0; e < m; e++ ) {
        cin >> edges[e].u >> edges[e].v >> edges[e].c >> edges[e].d;
        adjOut[edges[e].u].push_back( e );
        adjIn[edges[e].v].push_back( e );
    }

    specialEdge = -1;
    getDistances( 1, n, dist[1], used1 );
    getDistances( n, 1, dist[n], usedN );
    for ( int u = 1; u <= n; u++ ) {
        for ( int v = 1; v <= n; v++ )
            dist[u][v] = INF;
    }
    for ( int u = 1; u <= n; u++ )
        dist[u][u] = 0;
    for ( int e = 0; e < m; e++ )
        dist[edges[e].u][edges[e].v] = edges[e].c;
    for ( int w = 1; w <= n; w++ ) {
        for ( int u = 1; u <= n; u++ ) {
            for ( int v = 1; v <= n; v++ )
                dist[u][v] = min( dist[u][v], dist[u][w] + dist[w][v] );
        }
    }
    for ( int u = 1; u <= n; u++ )
        getDistances( u, 1, dist[u], usedNew );

    int minTotalCost = 2e9;
    if ( dist[1][n] < INF && dist[n][1] < INF )
        minTotalCost = dist[1][n] + dist[n][1];
    //printf( "0 durmuri: \n", dist[1][n] + dist[n][1] );
    for ( int e = 0; e < m; e++ ) {
        int u = edges[e].u, v = edges[e].v, c = edges[e].c;
        int newCost1N, newCostN1;
        if ( !used1[e] )
            newCost1N = min( dist[1][n], dist[1][v] + c + dist[u][n] );
        else {
            specialEdge = e;
            adjOut[v].push_back( e );
            swap( edges[e].u, edges[e].v );
            getDistances( 1, n, distNew, usedNew );
            newCost1N = distNew[n];
            swap( edges[e].u, edges[e].v );
            adjOut[v].pop_back();
        }
        if ( !usedN[e] )
            newCostN1 = min( dist[n][1], dist[n][v] + c + dist[u][1] );
        else {
            specialEdge = e;
            adjOut[v].push_back( e );
            swap( edges[e].u, edges[e].v );
            getDistances( n, 1, distNew, usedNew );
            newCostN1 = distNew[1];
            swap( edges[e].u, edges[e].v );
            adjOut[v].pop_back();
        }

        //printf( "drumul %d: %d %d %d\n", e, newCost1N, newCostN1, newCost1N + newCostN1 + edges[e].d );
        if ( newCost1N < INF && newCostN1 < INF )
            minTotalCost = min( minTotalCost, newCost1N + newCostN1 + edges[e].d );
    }

    cout << (minTotalCost >= INF ? - 1 : minTotalCost) << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63