oj.uz

Submission #924769

# Submission time Handle Problem Language Result Execution time Memory
924769 2024-02-09T16:05:52 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 214 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;
    }
    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=rdij2(1,n);
        temp=rdij2(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=rdij2(n,n);
        temp=rdij2(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,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(temp2[1],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:236:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  236 |         auto [a,b,c,d]=e[i];
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 6744 KB Output is correct
2 Correct 120 ms 6748 KB Output is correct
3 Correct 200 ms 6820 KB Output is correct
4 Correct 192 ms 6824 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 43 ms 6744 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 201 ms 6824 KB Output is correct
11 Correct 214 ms 6744 KB Output is correct
12 Correct 195 ms 6748 KB Output is correct
13 Incorrect 85 ms 6828 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 8920 KB Output is correct
2 Incorrect 209 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 180 ms 6744 KB Output is correct
2 Correct 131 ms 6748 KB Output is correct
3 Correct 183 ms 8920 KB Output is correct
4 Correct 133 ms 6788 KB Output is correct
5 Correct 183 ms 8920 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 178 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 177 ms 6744 KB Output is correct
2 Correct 120 ms 6748 KB Output is correct
3 Correct 200 ms 6820 KB Output is correct
4 Correct 192 ms 6824 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 43 ms 6744 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 201 ms 6824 KB Output is correct
11 Correct 214 ms 6744 KB Output is correct
12 Correct 195 ms 6748 KB Output is correct
13 Incorrect 85 ms 6828 KB Output isn't correct
14 Halted 0 ms 0 KB -