Submission #923571

#	Time	Username	Problem	Language	Result	Execution time	Memory
923571		noyancanturk	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1091 ms	2932 KiB

ho_t4

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+5;
#else
    const int lim=3e3+3;
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int mod=1e9+7;
//const int mod=(1ll<<61)-1;

using pii=pair<int,int>;
    
struct edge{
    int x,y,c,d;
};
    
template <>
struct std::hash<pii>{
    size_t operator()(const pii& k) const{
        int first=hash<int>()(k.first),second=hash<int>()(k.second);
        return hash<int>()(first^second);
    }
};
const int inf=INT_MAX*200ll;
inline void solve(){
    int n,m;
    cin>>n>>m;
    edge all[m];
    for(int i=0;i<m;i++){
        cin>>all[i].x>>all[i].y>>all[i].c>>all[i].d;
        all[i].x--,all[i].y--;
    }
    int dist[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=inf;
        }
    }
    for(int i=0;i<m;i++){
        dist[all[i].x][all[i].y]=min(
            all[i].c,
            dist[all[i].x][all[i].y]
        );
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j]=min(
                    dist[i][j],
                    dist[i][k]+dist[k][j]
                );
            }
        }
    }
    pii v[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            v[i][j]={inf,inf};
        }
    }
    for(auto[x,y,c,d]:all){
        if(c<v[x][y].second){
            v[x][y].second=c;
            if(v[x][y].second<v[x][y].first){
                swap(v[x][y].first,v[x][y].second);
            }
        }
    }
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cerr<<(v[i][j].first^inf?v[i][j].first:-1)<<" "<<(v[i][j].second^inf?v[i][j].second:-1)<<" | ";
        }cerr<<"\n";
    }
    */
    //cerr<<"ok\n";
    int ans=dist[0][n-1]+dist[n-1][0];
    //cerr<<ans<<"\n";
    for(auto[x,y,c,d]:all){
        //cerr<<"\n"<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n";
        if(dist[y][x]<=c)continue;
        //cerr<<dist[y][x]-c<<" "<<(dist[0][n-1]+dist[n-1][0])-ans<<"\n";
        pii p1=v[x][y],p2=v[y][x];
        if(v[x][y].first==c){
            swap(v[x][y].first,v[x][y].second);
        }
        if(c<v[y][x].second){
            v[y][x].second=c;
            if(v[y][x].second<v[y][x].first){
                swap(v[y][x].first,v[y][x].second);
            }
        }
        /*
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cerr<<(v[i][j].first^inf?v[i][j].first:-1)<<" | ";
            }cerr<<"\n";
        }
        */
        int curd[n];
        for(int i=0;i<n;i++){
            curd[i]=inf;
        }
        curd[0]=0;
        bool vis[n];
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n-1;i++){
            int mini=-1;
            for(int j=0;j<n;j++){
                if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
                    mini=j;
                }
            }
            vis[mini]=1;
            if(mini==n-1)break;
            for(int j=0;j<n;j++){
                curd[j]=min(
                    curd[j],
                    curd[mini]+v[mini][j].first
                );
            }
        }
        /*
        for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        cerr<<"\n";
        */
        if(curd[n-1]==inf){
            v[x][y]=p1;
            v[y][x]=p2;
            continue;
        }
        int ansnow=curd[n-1];
        for(int i=0;i<n;i++){
            curd[i]=inf;
        }
        curd[n-1]=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n-1;i++){
            int mini=-1;
            for(int j=0;j<n;j++){
                if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
                    mini=j;
                }
            }
            vis[mini]=1;
            if(!mini)break;
            for(int j=0;j<n;j++){
                curd[j]=min(
                    curd[j],
                    curd[mini]+v[mini][j].first
                );
            }
        }
        /*
        for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        cerr<<"\n";
        */
        if(curd[0]!=inf){
            ansnow+=curd[0]+d;
            ans=min(ans,ansnow);
        }
        //cerr<<ansnow<<"\n\n";
        v[x][y]=p1;
        v[y][x]=p2;
    }
    if(ans<inf-100)cout<<ans<<"\n";
    else cout<<"-1\n";
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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