Submission #690038

#	Time	Username	Problem	Language	Result	Execution time	Memory
690038		Paul_Liao_1457	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1081 ms	10100 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)(2e9+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];
ll dis[2][2][205],a[50005],b[50005],c[50005],d[50005],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<ll,pair<int,int> > > pq;
    pq.push({0,{1,0}});
    while(pq.size()){
        ll 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]){
            pq.push({t+c[i],{b[i],i}});
        }
    }
    pq.push({0,{n,0}});
    while(pq.size()){
        ll 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]){
            pq.push({t+c[i],{a[i],i}});
        }
    }
    pq.push({0,{n,0}});
    while(pq.size()){
        ll 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]){
            pq.push({t+c[i],{b[i],i}});
        }
    }
    pq.push({0,{1,0}});
    while(pq.size()){
        ll 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]){
            pq.push({t+c[i],{a[i],i}});
        }
    }
    ll ans=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]){
            PQ<pair<ll,int> > p;
            FOR(j,0,n+1) tmp[j]=INF;
            p.push({0,1});
            while(p.size()){
                ll now=p.top().S,t=p.top().F; p.pop();
                if(tmp[now]!=INF) continue;
                tmp[now]=t;
                for(auto j:e[0][now])if(j!=i){
                    if(j<=m) p.push({t+c[j],b[j]});
                    else if(j==i+m){
                        p.push({t+c[i],a[i]});
                    }
                }
            }
            d1=tmp[n];
        }
        else{
            d1=min(dis[0][0][n],dis[0][0][b[i]]+dis[0][1][a[i]]+c[i]);
        }
        if(used[1][i]){
            PQ<pair<ll,int> > p;
            FOR(j,0,n+1) tmp[j]=INF;
            p.push({0,n});
            while(p.size()){
                ll now=p.top().S,t=p.top().F; p.pop();
                if(tmp[now]!=INF) continue;
                tmp[now]=t;
                for(auto j:e[0][now])if(j!=i){
                    if(j<=m) p.push({t+c[j],b[j]});
                    else if(j==i+m){
                        p.push({t+c[i],a[i]});
                    }
                }
            }
            d2=tmp[1];
        }
        else{
            //cout<<"i="<<i<<endl;
            d2=min(dis[1][0][1],dis[1][0][b[i]]+dis[1][1][a[i]]+c[i]);
        }
        //cout<<"d1="<<d1<<" d2="<<d2<<endl;
        ans=min(ans,d1+d2+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: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63