oj.uz

Submission #924618

# Submission time Handle Problem Language Result Execution time Memory
924618 2024-02-09T10:12:30 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 200 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){
        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=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: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 165 ms 6824 KB Output is correct
2 Correct 111 ms 6788 KB Output is correct
3 Correct 171 ms 6992 KB Output is correct
4 Correct 175 ms 6748 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 38 ms 6748 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 180 ms 6748 KB Output is correct
11 Correct 184 ms 6824 KB Output is correct
12 Correct 179 ms 6744 KB Output is correct
13 Incorrect 78 ms 6744 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 8920 KB Output is correct
2 Incorrect 200 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 177 ms 7000 KB Output is correct
2 Correct 119 ms 6992 KB Output is correct
3 Correct 172 ms 8916 KB Output is correct
4 Correct 121 ms 6744 KB Output is correct
5 Correct 166 ms 8916 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Incorrect 170 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 165 ms 6824 KB Output is correct
2 Correct 111 ms 6788 KB Output is correct
3 Correct 171 ms 6992 KB Output is correct
4 Correct 175 ms 6748 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 38 ms 6748 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 180 ms 6748 KB Output is correct
11 Correct 184 ms 6824 KB Output is correct
12 Correct 179 ms 6744 KB Output is correct
13 Incorrect 78 ms 6744 KB Output isn't correct
14 Halted 0 ms 0 KB -