Submission #224208

#	Time	Username	Problem	Language	Result	Execution time	Memory
224208		lyc	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1093 ms	2688 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 int INF = 1e9;

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

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

void dijkstra(int s, vector<Edge>* al, int* 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;
    FOR(i,1,M){
        int U, V, C, D; cin >> U >> V >> C >> D;
        al[U].push_back({V,C,D,i});
    }

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

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

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