Submission #923544

#	Time	Username	Problem	Language	Result	Execution time	Memory
923544		noyancanturk	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1082 ms	7200 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]
                );
            }
        }
    }
    multiset<int>v[n][n];
    for(int i=0;i<m;i++){
        v[all[i].x][all[i].y].insert(all[i].c);
        if(2<v[all[i].x][all[i].y].size()){
            auto p=v[all[i].x][all[i].y].end();
            p--;
            v[all[i].x][all[i].y].erase(p);
        }
    }
    //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";
        auto p=v[x][y].find(c);
        if(p!=v[x][y].end())v[x][y].erase(v[x][y].find(c));
        v[y][x].insert(c);
        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++){
                if(v[mini][j].size()){
                    curd[j]=min(
                        curd[j],
                        curd[mini]+*v[mini][j].begin()
                    );
                }
            }
        }
        /*
        for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        cerr<<"\n";
        */
        if(curd[n-1]==inf){
            v[y][x].erase(v[y][x].find(c));
            v[x][y].insert(c);
            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++){
                if(v[mini][j].size()){
                    curd[j]=min(
                        curd[j],
                        curd[mini]+*v[mini][j].begin()
                    );
                }
            }
        }
        /*
        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";
        p=v[y][x].find(c);
        if(p!=v[y][x].end()){
            v[y][x].erase(v[y][x].find(c));
        }
        v[x][y].insert(c);
    }
    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