제출 #224107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224107		errorgorn	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	1095 ms	7012 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

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;
				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();
	
	//try dijk start and end
	ll ans=sf[n]+tf[1];
	
	if (m>1000){
		for (auto &it:edges){
			ans=min(ans,min(sf[n],sf[it.v]+it.len+tb[it.u])+min(tf[1],tf[it.v]+it.len+sb[it.u])+it.flip);
		}
		
		cout<<ans<<endl;
	}
	
	/*
	rep(x,1,n+1){
		cout<<sf[x]<<" "<<sb[x]<<" "<<tf[x]<<" "<<tb[x]<<endl;
	}
	*/
	
	rep(bad,0,m){
		//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();
	}
	
	if (ans>=INF) cout<<-1<<endl;
	else cout<<ans<<endl;
}

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