Submission #527026

#	Time	Username	Problem	Language	Result	Execution time	Memory
527026		AdamGS	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	799 ms	3816 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int MAXN=207, MAXM=5e4+7, INF=2e9+7;
vector<int>V[MAXN];
pair<pair<int,int>,pair<int,int>>T[MAXM];
int odl[MAXN][4], odw[MAXM], mi[MAXN], n, m;
void dijkstra1(int v, int r, int p) {
    rep(i, n) odl[i][p]=INF;
    priority_queue<pair<int,pair<int,int>>>q;
    q.push({0, {v, -1}});
    while(!q.empty()) {
        int o=-q.top().st, a=q.top().nd.st, b=q.top().nd.nd; q.pop();
        if(odl[a][p]<=o) continue;
        odl[a][p]=o;
        if(!r && b!=-1) odw[b]=1;
        for(auto i : V[a]) {
            if(!r) {
                if(T[i].st.st==a && odl[T[i].st.nd][p]==INF) {
                    q.push({-o-T[i].nd.st, {T[i].st.nd, i}});
                }
            } else {
                if(T[i].st.nd==a && odl[T[i].st.st][p]==INF) {
                    q.push({-o-T[i].nd.st, {T[i].st.st, i}});
                }
            }
        }
    }
}
void dijkstra2(int v) {
    rep(i, n) odl[i][0]=mi[i]=INF;
    mi[v]=0;
    while(true) {
        int o=INF, a=-1;
        rep(i, n) if(mi[i]<o && odl[i][0]==INF) {
            o=mi[i];
            a=i;
        }
        if(a==-1) break;
        odl[a][0]=o;
        for(auto i : V[a]) if(T[i].st.st==a) mi[T[i].st.nd]=min(mi[T[i].st.nd], o+T[i].nd.st);
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    rep(i, m) {
        cin >> T[i].st.st >> T[i].st.nd >> T[i].nd.st >> T[i].nd.nd;
        --T[i].st.st;
        --T[i].st.nd;
        V[T[i].st.st].pb(i);
        V[T[i].st.nd].pb(i);
    }
    dijkstra1(0, 0, 0);
    dijkstra1(0, 1, 1);
    dijkstra1(n-1, 0, 2);
    dijkstra1(n-1, 1, 3);
    int ans=INF;
    if(odl[n-1][0]<INF && odl[0][2]<INF) ans=odl[n-1][0]+odl[0][2];
    rep(i, m) if(!odw[i]) {
        int a=odl[n-1][0], b=odl[0][2];
        if(odl[T[i].st.nd][0]<INF && odl[T[i].st.st][3]<INF) {
            a=min(a, odl[T[i].st.nd][0]+odl[T[i].st.st][3]+T[i].nd.st);
        }
        if(odl[T[i].st.nd][2]<INF && odl[T[i].st.st][1]<INF) {
            b=min(b, odl[T[i].st.nd][2]+odl[T[i].st.st][1]+T[i].nd.st);
        }
        if(a<INF && b<INF) ans=min(ans, a+b+T[i].nd.nd);
    }
    rep(i, m) if(odw[i]) {
        swap(T[i].st.st, T[i].st.nd);
        dijkstra2(0);
        if(odl[n-1][0]<INF) {
            int akt=odl[n-1][0];
            dijkstra2(n-1);
            if(odl[0][0]<INF) {
                akt+=odl[0][0];
                ans=min(ans, akt+T[i].nd.nd);
            }
        }
        swap(T[i].st.st, T[i].st.nd);
    }
    cout << (ans==INF?-1:ans) << '\n';
}

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