제출 #1132421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132421		byunjaewoo	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	73 ms	6488 KiB

ho_t4

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

const int N=210, M=50010, INF=1e18;
int n, m, ans, d1[N], d2[N], dd1[N], dd2[N], d3[N], p1[N], p2[N], v1[M], v2[M];
vector<pair<int, int>> e[N][N];
int u[M], v[M], c[M], d[M];
bool c1[M], c2[M], chk[N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>u[i]>>v[i]>>c[i]>>d[i];
        e[u[i]][v[i]].push_back({c[i], i});
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) {
        e[i][j].push_back({INF, 0});
        sort(e[i][j].rbegin(), e[i][j].rend());
    }

    fill(d1+2, d1+n+1, INF), fill(chk+1, chk+n+1, false);
    for(int i=1; i<=n; i++) {
        int curr=0;
        for(int j=1; j<=n; j++) if(!chk[j] && (!curr || d1[curr]>d1[j])) curr=j;
        if(!curr) break;
        chk[curr]=true;
        for(int next=1; next<=n; next++) if(!chk[next] && d1[next]>d1[curr]+e[curr][next].back().first)
            d1[next]=d1[curr]+e[curr][next].back().first, p1[next]=e[curr][next].back().second;
    }
    if(d1[n]<INF) for(int i=n; i!=1; i=u[p1[i]]) c1[p1[i]]=true;

    fill(d2+1, d2+n, INF), fill(chk+1, chk+n+1, false);
    for(int i=1; i<=n; i++) {
        int curr=0;
        for(int j=1; j<=n; j++) if(!chk[j] && (!curr || d2[curr]>d2[j])) curr=j;
        if(!curr) break;
        chk[curr]=true;
        for(int next=1; next<=n; next++) if(!chk[next] && d2[next]>d2[curr]+e[curr][next].back().first)
            d2[next]=d2[curr]+e[curr][next].back().first, p2[next]=e[curr][next].back().second;
    }
    if(d2[1]<INF) for(int i=1; i!=n; i=u[p2[i]]) c2[p2[i]]=true;

    fill(dd1+2, dd1+n+1, INF), fill(chk+1, chk+n+1, false);
    for(int i=1; i<=n; i++) {
        int curr=0;
        for(int j=1; j<=n; j++) if(!chk[j] && (!curr || dd1[curr]>dd1[j])) curr=j;
        if(!curr) break;
        chk[curr]=true;
        for(int next=1; next<=n; next++) dd1[next]=min(dd1[next], dd1[curr]+e[next][curr].back().first);
    }

    fill(dd2+1, dd2+n, INF), fill(chk+1, chk+n+1, false);
    for(int i=1; i<=n; i++) {
        int curr=0;
        for(int j=1; j<=n; j++) if(!chk[j] && (!curr || dd2[curr]>dd2[j])) curr=j;
        if(!curr) break;
        chk[curr]=true;
        for(int next=1; next<=n; next++) dd2[next]=min(dd2[next], dd2[curr]+e[next][curr].back().first);
    }

    for(int i=1; i<=m; i++) {
        if(c1[i]) {
            bool flag=false;
            if(e[u[i]][v[i]].back().second==i) e[u[i]][v[i]].pop_back(), flag=true;
            if(e[v[i]][u[i]].back().first>c[i]) e[v[i]][u[i]].push_back({c[i], i});
            fill(d3+2, d3+n+1, INF), fill(chk+1, chk+n+1, false);
            for(int i=1; i<=n; i++) {
                int curr=0;
                for(int j=1; j<=n; j++) if(!chk[j] && (!curr || d3[curr]>d3[j])) curr=j;
                if(!curr) break;
                chk[curr]=true;
                for(int next=1; next<=n; next++) d3[next]=min(d3[next], d3[curr]+e[curr][next].back().first);
            }
            v1[i]=d3[n];
            if(flag) e[u[i]][v[i]].push_back({c[i], i});
            if(e[v[i]][u[i]].back().second==i) e[v[i]][u[i]].pop_back();
        }
        else v1[i]=min(d1[n], d1[v[i]]+dd2[u[i]]+c[i]);
    }

    for(int i=1; i<=m; i++) {
        if(c2[i]) {
            bool flag=false;
            if(e[u[i]][v[i]].back().second==i) e[u[i]][v[i]].pop_back(), flag=true;
            if(e[v[i]][u[i]].back().first>c[i]) e[v[i]][u[i]].push_back({c[i], i});
            fill(d3+1, d3+n, INF), d3[n]=0, fill(chk+1, chk+n+1, false);
            for(int i=1; i<=n; i++) {
                int curr=0;
                for(int j=1; j<=n; j++) if(!chk[j] && (!curr || d3[curr]>d3[j])) curr=j;
                if(!curr) break;
                chk[curr]=true;
                for(int next=1; next<=n; next++) d3[next]=min(d3[next], d3[curr]+e[curr][next].back().first);
            }
            v2[i]=d3[1];
            if(flag) e[u[i]][v[i]].push_back({c[i], i});
            if(e[v[i]][u[i]].back().second==i) e[v[i]][u[i]].pop_back();
        }
        else v2[i]=min(d2[1], d2[v[i]]+dd1[u[i]]+c[i]);
    }
    
    ans=d1[n]+d2[1];
    for(int i=1; i<=m; i++) ans=min(ans, v1[i]+v2[i]+d[i]);
    if(ans>=INF) ans=-1;
    cout<<ans;
    return 0;
}

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