Submission #1186560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186560		user736482	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	159 ms	5172 KiB

ho_t4

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define MAXN 17//207

ll a,b,c,d,t,n,m,ans,l;

vector<pair<pair<ll,ll>,pair<ll,ll>>>v;
vector<ll>g[207],g2[207],pth;
bool odw[207];
ll edg[207],dst[207],dst2[207];
ll dst3[207],dst4[207],dst5[207];
vector<ll>g3[207];
ll check(ll x){
    a=INFL;
    b=INFL;
    for(ll i=0;i<207;i++)g3[i].clear();
    swap(v[x].ff.ff,v[x].ff.ss);
    for(ll i=0;i<m;i++){
        g3[v[i].ff.ff].pb(i);
    }
    
    for(ll i=0;i<207;i++)dst3[i]=INFL;
    dst3[1]=0;
    for(ll i=0;i<n;i++){
        pair<ll,ll> bst={INFL,-1};
        for(ll j=1;j<=n;j++){
            if(dst3[j]!=-1)
            bst=min(bst,{dst3[j],j});
        }
        if(bst.ss==n){
            a=bst.ff;
            break;
        }
        for(ll j : g3[bst.ss]){
            dst3[v[j].ff.ss]=min(dst3[v[j].ff.ss],dst3[bst.ss]+v[j].ss.ff);
        }
        dst3[bst.ss]=-1;
        
    }
    for(ll i=0;i<207;i++)dst3[i]=INFL;
    dst3[n]=0;
    for(ll i=0;i<n;i++){
        pair<ll,ll> bst={INFL,-1};
        for(ll j=1;j<=n;j++){
            if(dst3[j]!=-1)
            bst=min(bst,{dst3[j],j});
        }
        if(bst.ss==1){
            b=bst.ff;
            break;
        }
        for(ll j : g3[bst.ss]){
            dst3[v[j].ff.ss]=min(dst3[v[j].ff.ss],dst3[bst.ss]+v[j].ss.ff);
        }
        dst3[bst.ss]=-1;
        
    }
    swap(v[x].ff.ff,v[x].ff.ss);
    //cout<<a<<" "<<b<<"\n";
    return a+b+v[x].ss.ss;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=0;i<207;i++){
        dst[i]=INFL;
        dst2[i]=INFL;
        dst3[i]=INFL;
        dst4[i]=INFL;
        dst5[i]=INFL;
    }
    for(ll i=0;i<m;i++){
        cin>>a>>b>>c>>d;
        v.pb({{a,b},{c,d}});
        g[a].pb(i);
        g2[b].pb(i);
    }
    v.pb({{-1,1},{0,0}});
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;//koszt,edge
    pq.push({0,m});
    ans=INFL;
    for(ll i=0;i<=n;i++)edg[i]=m;
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[v[pom.ss].ff.ss])continue; 
        if(v[pom.ss].ff.ss==n)ans=pom.ff;
        dst5[v[pom.ss].ff.ss]=pom.ff;
        odw[v[pom.ss].ff.ss]=1;
        edg[v[pom.ss].ff.ss]=pom.ss;
        for(ll i : g[v[pom.ss].ff.ss]){
            pq.push({pom.ff+v[i].ss.ff,i});
        }
    }   
    ll ak=n;
    for(ll i=1;i<=n;i++){
      //  cout<<edg[i]<<" "<<flush;
    }//return 0;
    if(edg[n]!=m)
    while(ak!=1){
        pth.pb(edg[ak]);
        //cout<<pth.back()<<" ";
        ak=v[edg[ak]].ff.ff;
    }//return 0;
    sort(pth.begin(),pth.end());
    v.back().ff.ss=n;
    pq.push({0,m});
    for(ll i=0;i<=n;i++)edg[i]=m;
    for(ll i=0;i<207;i++)odw[i]=0;
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[v[pom.ss].ff.ss])continue;
        dst[v[pom.ss].ff.ss]=pom.ff;
        odw[v[pom.ss].ff.ss]=1;
        edg[v[pom.ss].ff.ss]=pom.ss;
        for(ll i : g[v[pom.ss].ff.ss]){
            pq.push({pom.ff+v[i].ss.ff,i});
        }
    }   
    ak=1;
    for(ll i=1;i<=n;i++){
      //  cout<<edg[i]<<" "<<flush;
    }
    if(edg[1]!=m)
    while(ak!=n){
        
        pth.pb(edg[ak]);
        //cout<<pth.back()<<" ";
        ak=v[edg[ak]].ff.ff;
    }
    v.back().ff={1,-1};
    pq.push({0,m});
    for(ll i=0;i<207;i++)odw[i]=0;
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[v[pom.ss].ff.ff])continue;
        dst2[v[pom.ss].ff.ff]=pom.ff;
        odw[v[pom.ss].ff.ff]=1; 
        for(ll i : g2[v[pom.ss].ff.ff]){
            pq.push({pom.ff+v[i].ss.ff,i});
        }
    }
     v.back().ff={n,-1};
    pq.push({0,m});
    for(ll i=0;i<207;i++)odw[i]=0;
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[v[pom.ss].ff.ff])continue;
        dst4[v[pom.ss].ff.ff]=pom.ff;
        odw[v[pom.ss].ff.ff]=1; 
        for(ll i : g2[v[pom.ss].ff.ff]){
            pq.push({pom.ff+v[i].ss.ff,i});
        }
    }
    ans+=dst[1];
    sort(pth.begin(),pth.end());
  //  cout<<ans<<" ";
 // cout<<dst5[n]<<" "<<dst[1]<<"\n";
    for(ll i=0;i<m;i++){
        if(lower_bound(pth.begin(),pth.end(),i)!=pth.end() && *lower_bound(pth.begin(),pth.end(),i)==i)continue;
       // return 0;
     //  cout<<i<<" ";
      // cout<<ans<<" ";
     //   cout<<ans<<"  "<<v[i].ss.ff+dst4[v[i].ff.ff]+dst5[v[i].ff.ss]<<"\n";//return 0;
        ans=min(ans,min(dst5[n],v[i].ss.ff+dst4[v[i].ff.ff]+dst5[v[i].ff.ss])+min(dst[1],v[i].ss.ff+dst2[v[i].ff.ff]+dst[v[i].ff.ss])+v[i].ss.ss);
   //return 0;
    }//return  0;
    //cout<<ans<<" ";
    for(ll i : pth){
        //cout<<v[i].ss.ff<<" "<<v[i].ss.ss<<"\n";
     //   cout<<i<<" ";
        ans=min(ans,check(i));
        //cout<<ans<<" ";
    }
    if(ans>=INFL)ans=-1;
    cout<<ans;
   // cout<<"\n";
    for(ll i=0;i<n;i++){
     //   cout<<dst[i+1]<<" "<<dst2[i+1]<<" "<<dst3[i+1]<<" "<<dst4[i+1]<<" "<<dst5[i+1]<<"\n";
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63