oj.uz

Submission #923571

# Submission time Handle Problem Language Result Execution time Memory
923571 2024-02-07T12:21:58 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 2932 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;
        //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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1368 KB Output is correct
2 Correct 24 ms 1372 KB Output is correct
3 Correct 109 ms 1372 KB Output is correct
4 Correct 120 ms 1368 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 27 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 43 ms 1420 KB Output is correct
11 Correct 48 ms 1368 KB Output is correct
12 Correct 49 ms 1372 KB Output is correct
13 Correct 109 ms 1372 KB Output is correct
14 Correct 103 ms 1400 KB Output is correct
15 Correct 80 ms 1404 KB Output is correct
16 Correct 117 ms 1396 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 2932 KB Output is correct
2 Correct 269 ms 2784 KB Output is correct
3 Correct 177 ms 2908 KB Output is correct
4 Correct 66 ms 1372 KB Output is correct
5 Correct 95 ms 1404 KB Output is correct
6 Correct 60 ms 1372 KB Output is correct
7 Correct 41 ms 1372 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 1091 ms 2908 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1372 KB Output is correct
2 Correct 22 ms 1372 KB Output is correct
3 Correct 15 ms 2392 KB Output is correct
4 Correct 24 ms 1368 KB Output is correct
5 Correct 18 ms 2908 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1058 ms 2908 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1368 KB Output is correct
2 Correct 24 ms 1372 KB Output is correct
3 Correct 109 ms 1372 KB Output is correct
4 Correct 120 ms 1368 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 27 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 43 ms 1420 KB Output is correct
11 Correct 48 ms 1368 KB Output is correct
12 Correct 49 ms 1372 KB Output is correct
13 Correct 109 ms 1372 KB Output is correct
14 Correct 103 ms 1400 KB Output is correct
15 Correct 80 ms 1404 KB Output is correct
16 Correct 117 ms 1396 KB Output is correct
17 Correct 214 ms 2932 KB Output is correct
18 Correct 269 ms 2784 KB Output is correct
19 Correct 177 ms 2908 KB Output is correct
20 Correct 66 ms 1372 KB Output is correct
21 Correct 95 ms 1404 KB Output is correct
22 Correct 60 ms 1372 KB Output is correct
23 Correct 41 ms 1372 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Execution timed out 1091 ms 2908 KB Time limit exceeded
26 Halted 0 ms 0 KB -