Submission #690583

#	Time	Username	Problem	Language	Result	Execution time	Memory
690583		Paul_Liao_1457	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	331 ms	4300 KiB

ho_t4

//記得跳題
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
 
#define ll long long
#define LL __int128_t
#define DB double
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define INF (ll)(1e9+2e8+5)
#define MOD (ll)(1e9+7)
#define F first
#define S second
#define endl "\n"
#define AC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
template<class T> using PQ=priority_queue<T,vector<T>,greater<T> >;
 
void file(){
    freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
    freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
}

bool used[2][50005],vis[205];
int dis[2][2][205];
int a[50005],b[50005],c[50005],d[50005];
ll tmp[205];
vector<int> e[2][205];

signed main(){
    AC;
        int n,m; cin>>n>>m;
        FOR(i,1,m+1){
            cin>>a[i]>>b[i]>>c[i]>>d[i];
            e[0][a[i]].pb(i);
            e[0][b[i]].pb(i+m);
            e[1][b[i]].pb(i);
        }
        FOR(x,0,2)FOR(y,0,2)FOR(i,0,n+1) dis[x][y][i]=INF;
        PQ<pair<int,pair<int,int> > > pq;
        pq.push({0,{1,0}});
        while(pq.size()){
            int t=pq.top().F,now=pq.top().S.F,id=pq.top().S.S; pq.pop();
            if(dis[0][0][now]!=INF) continue;
            dis[0][0][now]=t; used[0][id]=1;
            for(auto i:e[0][now])if(i<=m){
                pq.push({t+c[i],{b[i],i}});
            }
        }
        pq.push({0,{n,0}});
        while(pq.size()){
            int t=pq.top().F,now=pq.top().S.F; pq.pop();
            if(dis[0][1][now]!=INF) continue;
            dis[0][1][now]=t;
            for(auto i:e[1][now])if(i<=m){
                pq.push({t+c[i],{a[i],i}});
            }
        }
        pq.push({0,{n,0}});
        while(pq.size()){
            int t=pq.top().F,now=pq.top().S.F,id=pq.top().S.S; pq.pop();
            if(dis[1][0][now]!=INF) continue;
            dis[1][0][now]=t; used[1][id]=1;
            for(auto i:e[0][now])if(i<=m){
                pq.push({t+c[i],{b[i],i}});
            }
        }
        pq.push({0,{1,0}});
        while(pq.size()){
            int t=pq.top().F,now=pq.top().S.F; pq.pop();
            if(dis[1][1][now]!=INF) continue;
            dis[1][1][now]=t;
            for(auto i:e[1][now])if(i<=m){
                pq.push({t+c[i],{a[i],i}});
            }
        }
        ll ans=(ll)dis[0][0][n]+dis[1][0][1];
    
    FOR(i,1,m+1){
        //cout<<"ans="<<ans<<endl;
        ll d1=INF,d2=INF;
        if(used[0][i]){
            FOR(j,0,n+2){
                tmp[j]=INF; vis[j]=0;
            }
            int now=n+1;
            tmp[1]=0;
            FOR(x,0,n){
                now=n+1;
                FOR(y,1,n+1)if(!vis[y]&&tmp[y]<tmp[now]){
                    now=y;
                }
                if(now==n+1) break;
                if(now==n) break;
                vis[now]=1;
                for(auto j:e[0][now])if(j!=i){
                    if(j<=m) tmp[b[j]]=min(tmp[b[j]],tmp[now]+c[j]);
                    else if(j==i+m) tmp[a[i]]=min(tmp[a[i]],tmp[now]+c[i]);
                }
            }
            d1=tmp[n];
        }
        else{
            //cout<<"hi"<<endl;
            d1=min((ll)dis[0][0][n],(ll)dis[0][0][b[i]]+dis[0][1][a[i]]+c[i]);
        }
        if(used[1][i]){
            FOR(j,0,n+2){
                tmp[j]=INF; vis[j]=0;
            }
            int now=n+1;
            tmp[n]=0;
            FOR(x,0,n){
                now=n+1;
                FOR(y,1,n+1)if(!vis[y]&&tmp[y]<tmp[now]){
                    now=y;
                }
                if(now==n+1) break;
                if(now==1) break;
                vis[now]=1;
                for(auto j:e[0][now])if(j!=i){
                    if(j<=m) tmp[b[j]]=min(tmp[b[j]],tmp[now]+c[j]);
                    else if(j==i+m) tmp[a[i]]=min(tmp[a[i]],tmp[now]+c[i]);
                }
            }
            d2=tmp[1];
        }
        else{
            //cout<<"i="<<i<<endl;
            d2=min((ll)dis[1][0][1],(ll)dis[1][0][b[i]]+dis[1][1][a[i]]+c[i]);
        }
         //cout<<"d1="<<d1<<" d2="<<d2<<endl;
        ans=min((ll)ans,((ll)d1+(ll)d2+(ll)d[i]));
    }
    if(ans>=INF) cout<<"-1"<<endl;
    else cout<<ans<<endl;
}

 
/*
 4 5
 1 2 4 4
 1 3 2 1
 4 3 1 2
 4 1 6 1
 2 4 2 5
 
 */

Compilation message (stderr)

ho_t4.cpp: In function 'void file()':
ho_t4.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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