Submission #224066

#	Time	Username	Problem	Language	Result	Execution time	Memory
224066		errorgorn	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1095 ms	7280 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
ll sb[205]; //source back
ll tf[205]; //sink front
ll tb[205]; //sink back

ll w1[205];
ll w2[205];

bool path[50005]; //is some edge in SP

int 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;
				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;
				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));
			}
		}
	}
}

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();
	
	/*
	rep(x,1,n+1){
		cout<<sf[x]<<" "<<sb[x]<<" "<<tf[x]<<" "<<tb[x]<<endl;
	}
	*/
	
	//try dijk start and end
	ll ans=sf[n]+tf[1];
	
	//find the path on best line from S->T
	if (sf[n]!=INF){
		memset(path,false,sizeof(path));
		int curr=n;
		
		while (curr!=1){
			for (auto &it:al_rev[curr]){
				if (sf[it.v]==sf[curr]-it.len){
					curr=it.v;
					path[it.id]=true;
					break;
				}
			}
		}
		
		for (auto &it:edges){
			if (path[it.id]) continue;
			ans=min(ans,sf[n]+tf[it.v]+sb[it.u]+it.len+it.flip);
		}
		
		rep(bad,0,m) if (path[bad]) {
			//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;
			
			al[edges[bad].v].push_back(E(-1,edges[bad].u,edges[bad].len,-1,-1));
			
			rep(x,0,205) w1[x]=w2[x]=INF;
			
			w1[1]=0;
			pq.push(ii(w1[1],1));
			while (!pq.empty()){
				temp=pq.top().first;
				node=pq.top().second;
				pq.pop();
				if (temp>w1[node]) continue; //important
				for (auto &it:al[node]){
					if (it.id==edges[bad].id) continue;
					if (w1[it.v]>w1[node]+it.len){
						w1[it.v]=w1[node]+it.len;
						pq.push(ii (w1[it.v],it.v));
					}
				}
			}
			
			w2[n]=0;
			pq.push(ii(w2[n],n));
			while (!pq.empty()){
				temp=pq.top().first;
				node=pq.top().second;
				pq.pop();
				if (temp>w2[node]) continue; //important
				for (auto &it:al[node]){
					if (it.id==edges[bad].id) continue;
					if (w2[it.v]>w2[node]+it.len){
						w2[it.v]=w2[node]+it.len;
						pq.push(ii (w2[it.v],it.v));
					}
				}
			}
			
			ans=min(ans,w1[n]+w2[1]+edges[bad].flip);
			al[edges[bad].v].pop_back();
		}
	}
	
	//find the path on best line from T->S
	if (tf[1]!=INF){
		memset(path,false,sizeof(path));
		int curr=1;
		
		while (curr!=n){
			for (auto &it:al_rev[curr]){
				if (tf[it.v]==tf[curr]-it.len){
					curr=it.v;
					path[it.id]=true;
					break;
				}
			}
		}
		
		for (auto &it:edges){
			if (path[it.id]) continue;
			ans=min(ans,tf[1]+sf[it.v]+tb[it.u]+it.len+it.flip);
		}
		
		rep(bad,0,m) if (path[bad]) {
			//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;
			
			al[edges[bad].v].push_back(E(-1,edges[bad].u,edges[bad].len,-1,-1));
			
			rep(x,0,205) w1[x]=w2[x]=INF;
			
			w1[1]=0;
			pq.push(ii(w1[1],1));
			while (!pq.empty()){
				temp=pq.top().first;
				node=pq.top().second;
				pq.pop();
				if (temp>w1[node]) continue; //important
				for (auto &it:al[node]){
					if (it.id==edges[bad].id) continue;
					if (w1[it.v]>w1[node]+it.len){
						w1[it.v]=w1[node]+it.len;
						pq.push(ii (w1[it.v],it.v));
					}
				}
			}
			
			w2[n]=0;
			pq.push(ii(w2[n],n));
			while (!pq.empty()){
				temp=pq.top().first;
				node=pq.top().second;
				pq.pop();
				if (temp>w2[node]) continue; //important
				for (auto &it:al[node]){
					if (it.id==edges[bad].id) continue;
					if (w2[it.v]>w2[node]+it.len){
						w2[it.v]=w2[node]+it.len;
						pq.push(ii (w2[it.v],it.v));
					}
				}
			}
			
			ans=min(ans,w1[n]+w2[1]+edges[bad].flip);
			al[edges[bad].v].push_back(E(-1,edges[bad].u,edges[bad].len,-1,-1));
		}
	}
	
	if (ans>=INF) cout<<-1<<endl;
	else cout<<ans<<endl;
}

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