oj.uz

Submission #923581

# Submission time Handle Problem Language Result Execution time Memory
923581 2024-02-07T12:31:49 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 76 ms 2936 KB 
#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;
        if(dist[y][x]-c<=(dist[0][n-1]+dist[n-1][0])-ans)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||ans<curd[mini]+d)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||ans<ansnow+curd[mini]+d)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;
            //cerr<<ansnow<<"\n";
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1372 KB Output is correct
2 Correct 24 ms 1400 KB Output is correct
3 Correct 7 ms 1372 KB Output is correct
4 Correct 7 ms 1368 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 27 ms 1284 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 37 ms 1420 KB Output is correct
11 Correct 46 ms 1396 KB Output is correct
12 Correct 17 ms 1420 KB Output is correct
13 Incorrect 8 ms 1372 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2908 KB Output is correct
2 Correct 76 ms 2936 KB Output is correct
3 Correct 20 ms 2904 KB Output is correct
4 Correct 48 ms 1372 KB Output is correct
5 Correct 63 ms 1372 KB Output is correct
6 Correct 58 ms 1392 KB Output is correct
7 Correct 42 ms 1372 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 18 ms 2908 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1372 KB Output is correct
2 Correct 6 ms 1372 KB Output is correct
3 Correct 15 ms 2396 KB Output is correct
4 Correct 27 ms 1372 KB Output is correct
5 Correct 17 ms 2840 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 18 ms 2908 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1372 KB Output is correct
2 Correct 24 ms 1400 KB Output is correct
3 Correct 7 ms 1372 KB Output is correct
4 Correct 7 ms 1368 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 27 ms 1284 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 37 ms 1420 KB Output is correct
11 Correct 46 ms 1396 KB Output is correct
12 Correct 17 ms 1420 KB Output is correct
13 Incorrect 8 ms 1372 KB Output isn't correct
14 Halted 0 ms 0 KB -