제출 #1326674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326674		JuanJL	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	551 ms	13564 KiB

ho_t4

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll; 

#ifdef D
	#define debug(x) cout << x
#else
	#define debug(x) // nothing
#endif

const int MAXN = 200+5;
const int MAXM = 50000+5;

#define INF ((ll)100000000000000)

ll n,m;

struct Ari{
	ll i;
	ll nd;
	ll to;
	ll cost;
	ll revcost;
	ll type;
	Ari(ll i=0, ll nd=0, ll to=0 , ll cost=0,ll revcost=0, ll type=0 ):i(i),nd(nd),to(to), cost(cost),revcost(revcost), type(type) {}
};

vector<Ari> adj[MAXN];
vector<Ari> radj[MAXN];
ll myInd[MAXM];
ll rmyInd[MAXM];
Ari ari[MAXM];
Ari revari[MAXM];

struct ResDijkstra{
	vector<ll> dis;
	vector<ll> myp;
	ResDijkstra(vector<ll> dis={}, vector<ll> myp={}):dis(dis),myp(myp){}
};

ResDijkstra dijkstra(ll nd){
	vector<ll> dis(n+2,INF);
	vector<ll> myp(n+2,INF);
	priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}}); dis[nd]=0;
	while(!pq.empty()){
		ll nd = pq.top().snd.fst;
		ll c = pq.top().fst*-1;
		ll p = pq.top().snd.snd;
		pq.pop();

		if(dis[nd]!=c) continue;
		debug(nd<<" "<<p<<'\n');

		for(auto a:adj[nd]){
			if(a.type==-1) continue;
			if(a.cost+c<dis[a.to]){
				dis[a.to]=a.cost+c;
				myp[a.to]=a.i;
				pq.push({ (a.cost+c)*-1, {a.to, a.i}});
			}
		}
	}
	return ResDijkstra(dis,myp);
}

ResDijkstra revdijkstra(ll nd){
	vector<ll> dis(n+2,INF);
	vector<ll> myp(n+2,INF);
	priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}}); dis[nd]=0;
	while(!pq.empty()){
		ll nd = pq.top().snd.fst;
		ll c = pq.top().fst*-1;
		ll p = pq.top().snd.snd;
		pq.pop();
		if(dis[nd]!=c) continue;
		for(auto a:radj[nd]){
			if(a.type==-1) continue;
			if(a.cost+c<dis[a.to]){
				dis[a.to]=a.cost+c;
				myp[a.to]=a.i;
				pq.push({ (a.cost+c)*-1, {a.to, a.i}});
			}
		}
	}
	return ResDijkstra(dis,myp);
}


bool way1toN[MAXM];
bool wayNto1[MAXM];

ll dis1toX[MAXN];
ll disXtoN[MAXN];
ll disXto1[MAXN];
ll disNtoX[MAXN];

ll myp1toX[MAXN];
ll mypNtoX[MAXN];

void recoverWay(){
	ll nd = 1;
	while(mypNtoX[nd]!=INF){
		wayNto1[mypNtoX[nd]]=true;
		nd = ari[mypNtoX[nd]].nd;
	}

	nd = n;
	while(myp1toX[nd]!=INF){
		way1toN[myp1toX[nd]]=true;
		nd = ari[myp1toX[nd]].nd;
	}
}

int main(){ FIN;
	cin>>n>>m;

	forn(i,1,m+1){	
		cin>>ari[i].nd;
		cin>>ari[i].to;
		cin>>ari[i].cost;
		cin>>ari[i].revcost;
		ari[i].type=1;
		ari[i].i=i;
		myInd[i]=SZ(adj[ari[i].nd]);

		adj[ari[i].nd].pb(ari[i]);

		Ari rari; // reverse arista
		rari.i=i;
		rari.nd=ari[i].to;
		rari.to=ari[i].nd;
		rari.cost=ari[i].cost;
		rari.revcost=ari[i].revcost;
		rari.type=1;
		rmyInd[i]=SZ(adj[rari.nd]);

		revari[i]=rari;
		
		radj[rari.nd].pb(rari);
	}

	debug("Precalculos\n");

	{	 // precalculos
		ResDijkstra aux;

		// 1 to X
		aux=dijkstra(1);
		forn(i,0,SZ(aux.dis)){
			dis1toX[i]=aux.dis[i];
			myp1toX[i]=aux.myp[i];
		}

		// N to x
		aux=dijkstra(n);
		forn(i,0,SZ(aux.dis)){
			disNtoX[i]=aux.dis[i];
			mypNtoX[i]=aux.myp[i];
		}

		debug("Fase 1 Lista\n");		
		//Recuperar los caminos
		recoverWay();

		debug("Fase 2 Lista\n");
		// X to N
		aux=revdijkstra(n);
		forn(i,0,SZ(aux.dis)){
			disXtoN[i]=aux.dis[i];
		}
		
		// X to 1
		aux=revdijkstra(1);
		forn(i,0,SZ(aux.dis)){
			disXto1[i]=aux.dis[i];
		}

		debug("Fase 3 Lista\n");
	}

	{
		// calcular respuesta
		ll best1toN = dis1toX[n];
		ll bestNto1 = disNtoX[1];

		ll res = INF;
		res=min(res, best1toN+bestNto1);
		
		forn(i,1,m+1){
			ll auxbest1toN = best1toN;
			ll auxbestNto1 = bestNto1;

			if(way1toN[i]){

				auxbest1toN = INF;

				adj[ari[i].nd][myInd[i]].type=-1;
				adj[ari[i].to].pb(revari[i]);

				ResDijkstra aux;
				aux=dijkstra(1);

				auxbest1toN=min(auxbest1toN,aux.dis[n]);
	
				adj[ari[i].nd][myInd[i]].type=1;
				adj[ari[i].to].pop_back();
				
			}else{
				auxbest1toN = min( auxbest1toN , dis1toX[ari[i].to] + disXtoN[ari[i].nd] + ari[i].cost );
			}
			
			if(wayNto1[i]){
				
				auxbestNto1 = INF;

				adj[ari[i].nd][myInd[i]].type=-1;
				adj[ari[i].to].pb(revari[i]);				

				ResDijkstra aux;
				aux=dijkstra(n);

				auxbestNto1=min(auxbestNto1,aux.dis[1]);

				adj[ari[i].nd][myInd[i]].type=1;
				adj[ari[i].to].pop_back();
				
			}else{
				auxbestNto1 = min( auxbestNto1 , disNtoX[ari[i].to] + disXto1[ari[i].nd] + ari[i].cost );
			}

			res=min( res , auxbest1toN+auxbestNto1+ari[i].revcost );
		}
		
		if(res==INF) res=-1;
		cout<<res<<'\n';
	}
	
	return 0;
}

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