Submission #224214

#	Time	Username	Problem	Language	Result	Execution time	Memory
224214		lyc	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	191 ms	4088 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 205;
const int MX_M = 5e4+5;

const long long INF = 1e18;

struct Edge { int v, c, d, i; };

int N, M;
vector<Edge> al[2][MX_N];
long long dist[4][MX_N];

void dijkstra(int s, vector<Edge>* al, long long* dist, int blocked) {
    fill(dist+1,dist+1+N,INF);
    dist[s] = 0;
    bool done[N+1];
    fill(done+1,done+1+N,0);
    while (true) {
        int u = -1;
        FOR(v,1,N) if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1) break;
        done[u] = 1;
        for (auto e : al[u]) if (e.i != blocked) {
            if (dist[u] + e.c < dist[e.v]) {
                dist[e.v] = dist[u] + e.c;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    if (M <= 1000) {
        FOR(i,1,M){
            int U, V, C, D; cin >> U >> V >> C >> D;
            al[0][U].push_back({V,C,D,i});
        }

        dijkstra(1,al[0],dist[0],-1);
        dijkstra(N,al[0],dist[1],-1);
        long long ans = min(INF, (long long) dist[0][N] + dist[1][1]);
        FOR(u,1,N){
            for (auto& e : al[0][u]) {
                al[0][e.v].push_back({u,e.c,e.d,M+1});
                dijkstra(1,al[0],dist[0],e.i);
                dijkstra(N,al[0],dist[1],e.i);
                al[0][e.v].pop_back();
                ans = min(ans, (long long) dist[0][N] + dist[1][1] + e.d);
            }
        }

        cout << (ans == INF ? -1 : ans) << '\n';
    } else {
        FOR(i,1,M){
            int U, V, C, D; cin >> U >> V >> C >> D;
            al[0][U].push_back({V,C,D,i});
            al[1][V].push_back({U,C,D,M+i});
        }

        dijkstra(1,al[0],dist[0],-1);
        dijkstra(1,al[1],dist[1],-1);
        dijkstra(N,al[0],dist[2],-1);
        dijkstra(N,al[1],dist[3],-1);
        long long ans = min(INF, (long long) dist[0][N] + dist[2][1]);
        FOR(u,1,N){
            for (auto& e : al[0][u]) {
                //TRACE(e.i _ dist[0][N] _ dist[2][e.v] _ dist[1][u] _ e.d);
                //TRACE(e.i _ dist[0][e.v] _ dist[3][u] _ dist[2][1] _ e.d);
                ans = min(ans, (long long) dist[0][N] + dist[2][e.v] + e.c + dist[1][u] + e.d);
                ans = min(ans, (long long) dist[0][e.v] + e.c + dist[3][u] + dist[2][1] + e.d);
            }
        }

        cout << (ans == INF ? -1 : ans) << '\n';
    }
}

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