제출 #1122798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122798		LucaIlie	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1095 ms	2116 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], used[MAX_N + 1][MAX_N + 1], usedNew[MAX_N + 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;
    for ( int s = 1; s <= n; s++ ) {
        int t = (s == 1 ? n : 1);
        getDistances( s, t, dist[s], used[s] );
    }

    int 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;

        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();

        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