Submission #1122804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122804		LucaIlie	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1082 ms	2116 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

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

struct vd {
    int v;
    unsigned d;

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

const int MAX_N = 200;
const int MAX_M = 5e4;
const int INF = 2e9;
int n;
bool vis[MAX_N + 1], used[MAX_N + 1][MAX_N + 1], usedNew[MAX_N + 1];
unsigned 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, unsigned 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;
    for ( int s = 1; s <= n; s++ ) {
        int t = (s == 1 ? n : 1);
        getDistances( s, t, dist[s], used[s] );
    }

    unsigned 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;
        unsigned newCost1N, newCostN1;
        if ( !used[1][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 ( !used[n][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 );
        minTotalCost = min( minTotalCost, newCost1N + newCostN1 + edges[e].d );
    }

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

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