Submission #1326478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326478		JuanJL	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	81 ms	10180 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 mset(a,v) memset(a,v,sizeof(a))
#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)20000000000000)

ll n,m;
vector<pair<ll,ll>> adj[MAXN];
vector<pair<ll,ll>> radj[MAXN];
ll cost[MAXM];
ll revc[MAXM];

pair<vector<ll>,vector<ll>> dijkstra(ll nd, ll t){
	vector<ll> dist(n,INF);
	vector<ll> pa(n,-1);
	priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}});
	while(!pq.empty()){
		ll nd = pq.top().snd.fst;
		ll c = pq.top().fst*-1;
		ll p = pq.top().snd.snd;
		pq.pop();

		if(dist[nd]<INF) continue;
		dist[nd]=c;
		pa[nd]=p;

		if(t==1){
			for(auto i:adj[nd]) if(i.snd>=0){
				pq.push({(c+cost[i.snd])*-1,{i.fst,nd}});
			}
		}else{
			for(auto i:radj[nd]) if(i.snd>=0){
				pq.push({(c+cost[i.snd])*-1,{i.fst,nd}});
			}
		}
	}

	return {dist,pa};
}


vector<ll> rd1N;
vector<ll> rdN1;
vector<ll> d1N;
vector<ll> p1N;
vector<ll> dN1;
vector<ll> pN1;

pair<ll,ll> ari[MAXM];
ll uind[MAXM];
ll vind[MAXM];
bool princ1N[MAXM];
bool princN1[MAXM];

void calcprincipal(){
	ll nd = n-1;
	while(p1N[nd]!=-1){
		forn(j,0,SZ(adj[p1N[nd]])){
			if(adj[p1N[nd]][j].fst==nd){
				princ1N[adj[p1N[nd]][j].snd]=true;
			}
		}
		nd=p1N[nd];
	}

	nd = 0;
	while(pN1[nd]!=-1){
		forn(j,0,SZ(adj[pN1[nd]])){
			if(adj[pN1[nd]][j].fst==nd){
				princN1[adj[pN1[nd]][j].snd]=true;
			}
		}
		nd=pN1[nd];
	}
}

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

	ll u,v;
	forn(i,1,m+1){
		cin>>u>>v; u--; v--;
		uind[i]=SZ(adj[u]);
		vind[i]=SZ(adj[v]);
		adj[u].pb({v,i}); ari[i]={u,v};
		adj[v].pb({u,-i});

		radj[v].pb({u,i});
		radj[u].pb({v,-i});
		
		cin>>cost[i];
		cin>>revc[i];
	}

	//cout<<"se llega\n";

	d1N = dijkstra(0,1).fst;
	p1N = dijkstra(0,1).snd;
	dN1 = dijkstra(n-1,1).fst;
	pN1 = dijkstra(n-1,1).snd;

	//cout<<"se llega\n";

	rd1N = dijkstra(0,0).fst;
	rdN1 = dijkstra(n-1,0).fst;

	//cout<<"se llega\n";	
	
	calcprincipal();

	//cout<<"se llega\n";
	ll b1N = d1N[n-1];
	ll bN1 = dN1[0];
	
	ll res = INF;
	res=min(res,d1N[n-1]+dN1[0]);
	/*cout<<d1N[n-1]<<" "<<dN1[0]<<'\n';
	cout<<res<<'\n';*/
	
	forn(i,0,n){
		for(auto j:adj[i]) debug(i<<"->"<<j.fst<<" "<<j.snd<<'\n');
	}
	

	forn(i,1,m+1){
		ll pb1N=b1N;
		ll pbN1=bN1;
		if(princ1N[i]){
			pb1N=INF;
			ll cost = revc[i];
			adj[ari[i].fst][uind[i]].snd*=-1;
			adj[ari[i].snd][vind[i]].snd*=-1;

			vector<ll> aux1N = dijkstra(0,1).fst;
			cost+=aux1N[n-1];

			adj[ari[i].fst][uind[i]].snd*=-1;
			adj[ari[i].snd][vind[i]].snd*=-1;

			pb1N=min(pb1N,cost);
		}else{
			//cout<<"-1\n";
			pb1N=min(pb1N,revc[i]+rdN1[ari[i].fst]+d1N[ari[i].snd]+cost[i]);
		}
		
		if(princN1[i]){
			pbN1=INF;
			ll cost = revc[i];
			adj[ari[i].fst][uind[i]].snd*=-1;
			adj[ari[i].snd][vind[i]].snd*=-1;
			
			vector<ll> auxN1 = dijkstra(n-1,1).fst;
			cost+=auxN1[0];

			adj[ari[i].fst][uind[i]].snd*=-1;
			adj[ari[i].snd][vind[i]].snd*=-1;	
		
			pbN1=min(pbN1,cost);
		}else{
			//cout<<"-2\n";
			pbN1=min(pbN1,revc[i]+rd1N[ari[i].fst]+dN1[ari[i].snd]+cost[i]);
		}

		//cout<<"dando vuelta "<<i<<" "<<pb1N<<" "<<pbN1<<'\n';
		res=min(res, pb1N+pbN1);
	}	

	if(res>=INF) res=-1;
	cout<<res<<'\n';
	return 0;
}

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