Submission #525042

#	Time	Username	Problem	Language	Result	Execution time	Memory
525042		mosiashvililuka	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	79 ms	9400 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
const long long N=200000009LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,C,D,A[50009],B[50009],dis[209][209],bo[50009],dis2[209][209],pas,z[209],zi,BO[50009],DIS[209][209],Adis[209][209];
pair <pair <long long, long long>, pair <long long, long long> > p[50009];
pair <long long, long long> P;
multiset <pair <pair <long long, long long>, long long> > v[209],V[209];
multiset <pair <pair <long long, long long>, long long> >::iterator it;
priority_queue <pair <long long, long long> > s;
void DJI(long long q){
	long long h,qw,we,er;
	for(h=1; h<=a; h++){
		dis[q][h]=N;bo[h]=0;
	}
	while(s.size()) s.pop();
	s.push({0,q});dis[q][q]=0;
	while(s.size()){
		while(s.size()){
			P=s.top();
			if(bo[P.second]==0) break;
			s.pop();
		}
		if(s.size()==0) break;
		qw=-P.first;we=P.second;bo[we]=1;
		s.pop();
		for(it=v[we].begin(); it!=v[we].end(); it++){
			if(dis[q][(*it).first.first]>dis[q][we]+(*it).first.second){
				dis[q][(*it).first.first]=dis[q][we]+(*it).first.second;
				dis2[q][(*it).first.first]=(*it).second;
				s.push({-dis[q][(*it).first.first],(*it).first.first});
			}
		}
	}
}
void ADJI(long long q){
	long long h,qw,we,er;
	for(h=1; h<=a; h++){
		Adis[q][h]=N;bo[h]=0;
	}
	while(s.size()) s.pop();
	s.push({0,q});Adis[q][q]=0;
	while(s.size()){
		while(s.size()){
			P=s.top();
			if(bo[P.second]==0) break;
			s.pop();
		}
		if(s.size()==0) break;
		qw=-P.first;we=P.second;bo[we]=1;
		s.pop();
		for(it=V[we].begin(); it!=V[we].end(); it++){
			if(Adis[q][(*it).first.first]>Adis[q][we]+(*it).first.second){
				Adis[q][(*it).first.first]=Adis[q][we]+(*it).first.second;
				s.push({-Adis[q][(*it).first.first],(*it).first.first});
			}
		}
	}
}
//
void DJI2(long long q){
	long long h,qw,we,er;
	for(h=1; h<=a; h++){
		DIS[q][h]=N;bo[h]=0;
	}
	while(s.size()) s.pop();
	s.push({0,q});DIS[q][q]=0;
	while(s.size()){
		while(s.size()){
			P=s.top();
			if(bo[P.second]==0) break;
			s.pop();
		}
		if(s.size()==0) break;
		qw=-P.first;we=P.second;bo[we]=1;
		s.pop();
		for(it=v[we].begin(); it!=v[we].end(); it++){
			if(DIS[q][(*it).first.first]>DIS[q][we]+(*it).first.second){
				DIS[q][(*it).first.first]=DIS[q][we]+(*it).first.second;
				s.push({-DIS[q][(*it).first.first],(*it).first.first});
			}
		}
	}
}
//
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=b; i++){
		cin>>c>>d>>C>>D;
		p[i]={{c,d},{C,D}};
		v[c].insert({{d,C},i});
		V[d].insert({{c,C},i});
	}
	DJI(1);
	DJI(a);
	ADJI(1);
	ADJI(a);
	if(dis[1][a]!=N&&dis[a][1]!=N) pas=dis[1][a]+dis[a][1]; else pas=N;
	if(1==0){
		cout<<dis[1][a]<<" "<<dis[a][1]<<endl;
		cout<<dis2[1][a]<<" "<<dis2[a][1]<<endl;
		cout<<pas<<endl;
		return 0;
	}
	for(i=1; i<=b; i++){
		BO[i]=0;
	}
	c=a;
	while(c!=1&&c!=0){
		zi++;z[zi]=dis2[1][c];
		e=dis2[1][c];
		if(p[e].first.first!=c){
			c=p[e].first.first;
		}else{
			c=p[e].first.second;
		}
	}
	for(i=1; i<=zi; i++) BO[z[i]]=1;
	A[0]=dis[1][a];
	for(i=1; i<=b; i++){
		if(BO[i]==1) continue;
		if(dis[1][p[i].first.second]!=N&&Adis[a][p[i].first.first]!=N) A[i]=dis[1][p[i].first.second]+p[i].second.first+Adis[a][p[i].first.first]; else A[i]=N;
		A[i]=min(A[i],dis[1][a]);
	}
	for(i=1; i<=b; i++){
		if(BO[i]==0) continue;
		it=v[p[i].first.first].lower_bound({{p[i].first.second,p[i].second.first},i});
		v[p[i].first.first].erase(it);
		v[p[i].first.second].insert({{p[i].first.first,p[i].second.first},i});
		DJI2(1);
		A[i]=DIS[1][a];
		it=v[p[i].first.second].lower_bound({{p[i].first.first,p[i].second.first},i});
		v[p[i].first.second].erase(it);
		v[p[i].first.first].insert({{p[i].first.second,p[i].second.first},i});
	}
	//
	/*for(i=0; i<=b; i++){
		cout<<A[i]<<"\n";
	}*/
	//
	
	
	for(i=1; i<=b; i++){
		BO[i]=0;
	}
	c=1;
	while(c!=a&&c!=0){
		zi++;z[zi]=dis2[a][c];
		e=dis2[a][c];
		if(p[e].first.first!=c){
			c=p[e].first.first;
		}else{
			c=p[e].first.second;
		}
	}
	for(i=1; i<=zi; i++) BO[z[i]]=1;
	B[0]=dis[a][1];
	for(i=1; i<=b; i++){
		if(BO[i]==1) continue;
		if(dis[a][p[i].first.second]!=N&&Adis[1][p[i].first.first]!=N) B[i]=dis[a][p[i].first.second]+p[i].second.first+Adis[1][p[i].first.first]; else B[i]=N;
		B[i]=min(B[i],dis[1][a]);
	}
	for(i=1; i<=b; i++){
		if(BO[i]==0) continue;
		it=v[p[i].first.first].lower_bound({{p[i].first.second,p[i].second.first},i});
		v[p[i].first.first].erase(it);
		v[p[i].first.second].insert({{p[i].first.first,p[i].second.first},i});
		DJI2(a);
		B[i]=DIS[a][1];
		it=v[p[i].first.second].lower_bound({{p[i].first.first,p[i].second.first},i});
		v[p[i].first.second].erase(it);
		v[p[i].first.first].insert({{p[i].first.second,p[i].second.first},i});
	}
	//
	/*for(i=0; i<=b; i++){
		cout<<B[i]<<"\n";
	}*/
	//
	for(i=0; i<=b; i++){
		//pas=min(pas,A[i]+B[i]+p[i].second.second);
		if(A[i]!=N&&B[i]!=N){
			pas=min(pas,A[i]+B[i]+p[i].second.second);
		}
	}
	if(pas!=N) cout<<pas; else cout<<-1;
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'void DJI(long long int)':
ho_t4.cpp:11:14: warning: variable 'qw' set but not used [-Wunused-but-set-variable]
   11 |  long long h,qw,we,er;
      |              ^~
ho_t4.cpp:11:20: warning: unused variable 'er' [-Wunused-variable]
   11 |  long long h,qw,we,er;
      |                    ^~
ho_t4.cpp: In function 'void ADJI(long long int)':
ho_t4.cpp:36:14: warning: variable 'qw' set but not used [-Wunused-but-set-variable]
   36 |  long long h,qw,we,er;
      |              ^~
ho_t4.cpp:36:20: warning: unused variable 'er' [-Wunused-variable]
   36 |  long long h,qw,we,er;
      |                    ^~
ho_t4.cpp: In function 'void DJI2(long long int)':
ho_t4.cpp:61:14: warning: variable 'qw' set but not used [-Wunused-but-set-variable]
   61 |  long long h,qw,we,er;
      |              ^~
ho_t4.cpp:61:20: warning: unused variable 'er' [-Wunused-variable]
   61 |  long long h,qw,we,er;
      |                    ^~

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