oj.uz

Submission #924771

# Submission time Handle Problem Language Result Execution time Memory
924771 2024-02-09T16:08:28 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 213 ms 9000 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
struct edge{
    int a,b,c,d;
};
const int mxn=405;
vector<edge>e;
vector<int>temp;
pii parent[mxn];
int id[mxn];
pair<pii,int> w[mxn][mxn];
pair<pii,int> scd[mxn][mxn];
map<pii,bool>mp;
void upd(pair<pii,int> &p,int x,int y,int z,int a,int b){
    if(x<p.F.F){
        scd[a][b]=p;
        p={{x,y},z};
    }
    else if(x==p.F.F and y<p.F.S){
        scd[a][b]=p;
        p.F.S=y;
        p.S=z;
    }
    else if(x==p.F.F or x<scd[a][b].F.F or (x==scd[a][b].F.F and y<scd[a][b].F.S)){
        scd[a][b]={{x,y},z};
    }
}
vector<int> dij(int st,int n){
    vector<int>dis(mxn);
    for(int i=0;i<mxn;i++)dis[i]=1e15;
    dis[st]=0;
    for(int i=1;i<=n;i++){
        parent[i]={-1,8e18};
    }
    vector<bool>used(n+1,0);
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(used[j])continue;
            if(t==-1 or dis[j]<dis[t]){
                t=j;
            }
        }
        used[t]=1;
        for(int j=1;j<=n;j++){
            if(dis[t]+w[t][j].F.F<dis[j]){
                dis[j]=dis[t]+w[t][j].F.F;
                parent[j]={t,w[t][j].F.F+w[t][j].F.S};
                id[j]=w[t][j].S;
            }
            else if(dis[t]+w[t][j].F.F==dis[j] and w[t][j].F.F+w[t][j].F.S<parent[j].S){
                parent[j]={t,w[t][j].F.F+w[t][j].F.S};
                id[j]=w[t][j].S;
            }
        }
    }
    return dis;
}
vector<int> rdij(int st,int n){
    vector<int>dis(mxn);
    for(int i=0;i<mxn;i++)dis[i]=1e15;
    dis[st]=0;
    for(int i=1;i<=n;i++){
        parent[i]={-1,1e15};
    }
    vector<bool>used(n+1,0);
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(used[j])continue;
            if(t==-1 or dis[j]<dis[t]){
                t=j;
            }
        }
        used[t]=1;
        for(int j=1;j<=n;j++){
            if(dis[t]+w[j][t].F.F<dis[j]){
                dis[j]=dis[t]+w[j][t].F.F;
                parent[j]={t,w[j][t].F.F+w[j][t].F.S};
                id[j]=w[j][t].S;
            }
            else if(dis[t]+w[j][t].F.F==dis[j] and w[j][t].F.F+w[j][t].F.S<parent[j].S){
                parent[j]={t,w[j][t].F.F+w[j][t].F.S};
                id[j]=w[j][t].S;
            }
        }
    }
    return dis;
}
vector<int> dij2(int st,int n){
    vector<int>dis(mxn);
    for(int i=0;i<mxn;i++)dis[i]=1e15;
    dis[st]=0;
    vector<bool>used(n+1,0);
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(used[j])continue;
            if(t==-1 or dis[j]<dis[t]){
                t=j;
            }
        }
        used[t]=1;
        for(int j=1;j<=n;j++){
            if(dis[t]+w[t][j].F.F<dis[j]){
                dis[j]=dis[t]+w[t][j].F.F;
            }
        }
    }
    return dis;
}vector<int> rdij2(int st,int n){
    vector<int>dis(mxn);
    for(int i=0;i<mxn;i++)dis[i]=1e15;
    dis[st]=0;
    vector<bool>used(n+1,0);
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(used[j])continue;
            if(t==-1 or dis[j]<dis[t]){
                t=j;
            }
        }
        used[t]=1;
        for(int j=1;j<=n;j++){
            if(dis[t]+w[j][t].F.F<dis[j]){
                dis[j]=dis[t]+w[j][t].F.F;
            }
        }
    }
    return dis;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        parent[i]={-1,-1};
        for(int j=1;j<=n;j++){
            w[i][j]={{1e18,1e18},1e18};
            scd[i][j]=w[i][j];
        }
    }
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        e.pb({a,b,c,d});
        upd(w[a][b],c,d,i,a,b);
    }
    vector<int>temp2;
    temp2=dij2(n,n);
    temp=dij(1,n);
    int ans=temp[n]+temp2[1];
    vector<bool>used(m+1,0);
    for(int i=1;i<=n;i++){
        //cout<<w[parent[i].F][]<<' ';
        if(parent[i].F==-1)continue;
        auto x=w[parent[i].F][i];
        auto y=x;
        used[x.S]=1;
        w[parent[i].F][i]=scd[parent[i].F][i];
        //w[parent[i].F][i]=
        x=w[i][parent[i].F];
        w[i][parent[i].F].F.F=min(parent[i].S,w[i][parent[i].F].F.F);
        temp2=dij2(n,n);
        temp=dij2(1,n);
        ans=min(ans,temp[n]+temp2[1]);
        w[i][parent[i].F]=x;
        w[parent[i].F][i]=y;
    }
    temp=rdij(n,n);
    for(int i=1;i<=n;i++){
        if(parent[i].F==-1)continue;
        auto x=w[i][parent[i].F];
        auto y=x;
        used[x.S]=1;
        w[i][parent[i].F]=scd[i][parent[i].F];
        x=w[parent[i].F][i];
        w[parent[i].F][i].F.F=min(parent[i].S,w[parent[i].F][i].F.F);
        temp2=dij2(1,n);
        temp=dij2(n,n);
        ans=min(ans,temp[1]+temp2[n]);
        w[parent[i].F][i]=x;
        w[i][parent[i].F]=y;
    }
    temp=rdij(1,n);
    for(int i=1;i<=n;i++){
        if(parent[i].F==-1)continue;
        auto x=w[i][parent[i].F];
        auto y=x;
        w[i][parent[i].F]=scd[i][parent[i].F];
        used[x.S]=1;
        x=w[parent[i].F][i];
        w[parent[i].F][i].F.F=min(parent[i].S,w[parent[i].F][i].F.F);
        temp2=dij2(n,n);
        temp=dij2(1,n);
        ans=min(ans,temp[n]+temp2[1]);
        w[parent[i].F][i]=x;
        w[i][parent[i].F]=y;
    }
    temp=dij(n,n);
    for(int i=1;i<=n;i++){
        if(parent[i].F==-1)continue;
        auto x=w[parent[i].F][i];
        used[x.S]=1;
        auto y=w[parent[i].F][i];
        w[parent[i].F][i]=scd[parent[i].F][i];
        x=w[i][parent[i].F];
        w[i][parent[i].F].F.F=min(parent[i].S,w[i][parent[i].F].F.F);
        temp2=dij2(1,n);
        temp=dij2(n,n);
        ans=min(ans,temp[1]+temp2[n]);
        w[i][parent[i].F]=x;
        w[parent[i].F][i]=y;
    }
    temp2=dij(n,1);
    int x=temp2[1];
    temp2=rdij(n,n);
    temp=dij(1,n);
    for(int i=0;i<m;i++){
        if(used[i])continue;
        auto [a,b,c,d]=e[i];
        ans=min(ans,min(temp[n],temp[b]+c+temp2[a])+min(x,temp2[b]+c+temp[a])+d);
        //cout<<ans<<'\n';
    }
    if(ans>=(int)1e15){
        cout<<-1<<'\n';
        return 0;
    }
    cout<<ans<<'\n';
}
/*
*/

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:238:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  238 |         auto [a,b,c,d]=e[i];
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 6748 KB Output is correct
2 Correct 121 ms 6784 KB Output is correct
3 Correct 174 ms 6748 KB Output is correct
4 Correct 175 ms 6744 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 42 ms 6748 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 206 ms 6744 KB Output is correct
11 Correct 175 ms 6748 KB Output is correct
12 Correct 174 ms 6748 KB Output is correct
13 Incorrect 76 ms 6820 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 8920 KB Output is correct
2 Incorrect 193 ms 8920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 6820 KB Output is correct
2 Correct 113 ms 6748 KB Output is correct
3 Correct 164 ms 8920 KB Output is correct
4 Correct 117 ms 6748 KB Output is correct
5 Correct 172 ms 9000 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 160 ms 8920 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 6748 KB Output is correct
2 Correct 121 ms 6784 KB Output is correct
3 Correct 174 ms 6748 KB Output is correct
4 Correct 175 ms 6744 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 42 ms 6748 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 206 ms 6744 KB Output is correct
11 Correct 175 ms 6748 KB Output is correct
12 Correct 174 ms 6748 KB Output is correct
13 Incorrect 76 ms 6820 KB Output isn't correct
14 Halted 0 ms 0 KB -