제출 #224771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224771		errorgorn	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	661 ms	8040 KiB

ho_t4

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=start-(start>end);x!=end-(start>end);x+=(start<end?1:-1))
#define all(x) x.begin(),x.end()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a, Args... args) { return max(a,MAX(args...)); }
template<typename... Args>
ll MIN(ll a, Args... args) { return min(a,MIN(args...)); }

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

const ll INF=1e18;

struct E{
	int u,v;
	ll len,flip;
	int id;

	E(int a,int b,int c,int d,int e){
		u=a,v=b;
		len=c,flip=d;
		id=e;
	}
};

int n,m;
vector<E> al[205];
vector<E> al_rev[205]; //store reversed edges
vector<E> edges;

priority_queue<ii,vector<ii>,greater<ii> > pq;
ll sf[205]; //source front
int ps[205]; //parent front
ll sb[205]; //source back
int pt[205]; //parent back
ll tf[205]; //sink front
ll tb[205]; //sink back

ll w[205];

map<int,ll> sp_f,sp_b; //is some edge in SP

ll temp,node; //stuff for dijk

void initial_d(){ //epic name
	rep(x,0,205) sf[x]=sb[x]=tf[x]=tb[x]=INF;
	
	sf[1]=0;
	pq.push(ii(sf[1],1));
	while (!pq.empty()){
		temp=pq.top().first;
		node=pq.top().second;
		pq.pop();
		if (temp>sf[node]) continue; //important
		for (auto &it:al[node]){
			if (sf[it.v]>sf[node]+it.len){
				sf[it.v]=sf[node]+it.len;
				ps[it.v]=it.id;
				pq.push(ii (sf[it.v],it.v));
			}
		}
	} 
	
	sb[1]=0;
	pq.push(ii(sb[1],1));
	while (!pq.empty()){
		temp=pq.top().first;
		node=pq.top().second;
		pq.pop();
		if (temp>sb[node]) continue; //important
		for (auto &it:al_rev[node]){
			if (sb[it.v]>sb[node]+it.len){
				sb[it.v]=sb[node]+it.len;
				pq.push(ii (sb[it.v],it.v));
			}
		}
	} 
	
	tf[n]=0;
	pq.push(ii(tf[n],n));
	while (!pq.empty()){
		temp=pq.top().first;
		node=pq.top().second;
		pq.pop();
		if (temp>tf[node]) continue; //important
		for (auto &it:al[node]){
			if (tf[it.v]>tf[node]+it.len){
				tf[it.v]=tf[node]+it.len;
				pt[it.v]=it.id;
				pq.push(ii (tf[it.v],it.v));
			}
		}
	} 
	
	tb[n]=0;
	pq.push(ii(tb[n],n));
	while (!pq.empty()){
		temp=pq.top().first;
		node=pq.top().second;
		pq.pop();
		if (temp>tb[node]) continue; //important
		for (auto &it:al_rev[node]){
			if (tb[it.v]>tb[node]+it.len){
				tb[it.v]=tb[node]+it.len;
				pq.push(ii (tb[it.v],it.v));
			}
		}
	}
}

void SP_d(){
	if (sf[n]!=INF){ //find best from S to T
		int curr=n;
		
		while (curr!=1){
			//debug(ps[curr]);
			sp_f[ps[curr]]=INF;
			curr=edges[ps[curr]].u;
		}
		
		for (auto &it2:sp_f){
			//we run a new iteration of dijkstra for this where we flip every edge on the SP
			//cout<<edges[bad].u<<" "<<edges[bad].v<<endl;
			rep(x,0,205) w[x]=INF;
			
			w[1]=0;
			pq.push(ii(w[1],1));
			while (!pq.empty()){
				temp=pq.top().first;
				node=pq.top().second;
				pq.pop();
				if (temp>w[node]) continue; //important
				for (auto &it:al[node]){
					if (it.id==it2.first) continue;
					if (w[it.v]>w[node]+it.len){
						w[it.v]=w[node]+it.len;
						pq.push(ii (w[it.v],it.v));
					}
				}
			}
			it2.second=w[n];
		}
	}
	
	//find the path on best line from T->S
	if (tf[1]!=INF){
		int curr=1;
		
		while (curr!=n){
			//debug(pt[curr]);
			sp_b[pt[curr]]=INF;
			curr=edges[pt[curr]].u;
		}
		
		for (auto &it2:sp_b) {
			//we run a new iteration of dijkstra for this where we flip every edge on the SP
			//cout<<edges[bad].u<<" "<<edges[bad].v<<endl;
			
			rep(x,0,205) w[x]=INF;
			
			w[n]=0;
			pq.push(ii(w[n],n));
			while (!pq.empty()){
				temp=pq.top().first;
				node=pq.top().second;
				pq.pop();
				if (temp>w[node]) continue; //important
				for (auto &it:al[node]){
					if (it.id==it2.first) continue;
					if (w[it.v]>w[node]+it.len){
						w[it.v]=w[node]+it.len;
						pq.push(ii (w[it.v],it.v));
					}
				}
			}

			it2.second=w[1];
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	int a,b,c,d;
	rep(x,0,m){
		cin>>a>>b>>c>>d;
		
		al[a].push_back(E(a,b,c,d,x));
		al_rev[b].push_back(E(b,a,c,d,x));
		edges.push_back(E(a,b,c,d,x));
	}
	
	initial_d();
	
	SP_d();
	
	//try dijk start and end
	ll ans=sf[n]+tf[1];
	
	for (auto &it:edges){
		ans=min(ans,(sp_f.count(it.id)?sp_f[it.id]:min(sf[n],sf[it.v]+tb[it.u]+it.len))+(sp_b.count(it.id)?sp_b[it.id]:min(tf[1],tf[it.v]+sb[it.u]+it.len))+it.flip);
		//debug(min((sp_f.count(it.id)?sp_f[it.id]:sf[n]),sf[it.v]+tb[it.u]+it.len));
		//debug(min((sp_b.count(it.id)?sp_b[it.id]:tf[1]),tf[it.v]+sb[it.u]+it.len));
	}
	
	if (ans>=INF) cout<<-1<<endl;
	else cout<<ans<<endl;
}

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