oj.uz

Submission #924617

# Submission time Handle Problem Language Result Execution time Memory
924617 2024-02-09T10:08:39 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 216 ms 8920 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;
    }
}
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=rdij2(1,n);
        temp=dij2(1,n);
        ans=min(ans,temp[n]+temp2[n]);
        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(n,n);
        temp=rdij2(n,n);
        ans=min(ans,temp[1]+temp2[1]);
        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(1,n);
        temp=rdij2(1,n);
        ans=min(ans,temp[n]+temp2[n]);
        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=rdij2(n,n);
        temp=dij2(n,n);
        ans=min(ans,temp[1]+temp2[1]);
        w[i][parent[i].F]=x;
        w[parent[i].F][i]=y;
    }
    temp2=dij(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+d+temp2[a])+min(temp2[1],temp2[b]+c+d+temp[a]));
        //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:233:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  233 |         auto [a,b,c,d]=e[i];
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 6836 KB Output is correct
2 Correct 119 ms 6748 KB Output is correct
3 Correct 181 ms 6748 KB Output is correct
4 Correct 186 ms 6820 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 40 ms 6748 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 194 ms 6824 KB Output is correct
11 Correct 200 ms 6824 KB Output is correct
12 Correct 189 ms 6828 KB Output is correct
13 Incorrect 95 ms 6748 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 8916 KB Output is correct
2 Incorrect 201 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 6748 KB Output is correct
2 Correct 129 ms 6780 KB Output is correct
3 Correct 180 ms 8920 KB Output is correct
4 Correct 134 ms 6784 KB Output is correct
5 Correct 183 ms 8916 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Incorrect 216 ms 8864 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 6836 KB Output is correct
2 Correct 119 ms 6748 KB Output is correct
3 Correct 181 ms 6748 KB Output is correct
4 Correct 186 ms 6820 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 40 ms 6748 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 194 ms 6824 KB Output is correct
11 Correct 200 ms 6824 KB Output is correct
12 Correct 189 ms 6828 KB Output is correct
13 Incorrect 95 ms 6748 KB Output isn't correct
14 Halted 0 ms 0 KB -