Submission #534542

#	Time	Username	Problem	Language	Result	Execution time	Memory
534542		alvingogo	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	59 ms	5836 KiB

ho_t4

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

const long long inf=4.9e15;
struct eg{
	int v,id,c,d;
};
vector<vector<eg> > e;
vector<int> p[2];
vector<int> dz[2];
int n;
int dijk(int x,int y,int t){
	p_q<pair<int,int> > pq;
	vector<int> dis(n,inf);
	dis[x]=0;
	pq.push({0,x});
	while(!pq.empty()){
		auto h=pq.top();
		pq.pop();
		if(dis[h.sc]!=h.fs){
			continue;
		}
		for(auto a:e[h.sc]){
			if(dis[a.v]>dis[h.sc]+a.c){
				dis[a.v]=dis[h.sc]+a.c;
				if(t<2){
					p[t][a.v]=a.id;
				}
				pq.push({dis[a.v],a.v});
			}
		}
	}
	if(t<2){
		dz[t]=dis;
	}
	return dis[y];
}
pair<vector<int>,vector<int> > fw(vector<vector<int> >& ez){
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				ez[i][j]=min(ez[i][j],ez[i][k]+ez[k][j]);
			}
		}
	}
	vector<int> d1(n),d2(n);
	for(int i=0;i<n;i++){
		d1[i]=ez[i][n-1];
		d2[i]=ez[i][0];
	}
	return {d1,d2};
}
signed main(){
	AquA;
	int m;
	cin >> n >> m;
	e.resize(n);
	p[0].resize(n);
	p[1].resize(n);
	vector<vector<int> > ez(n,vector<int>(n,inf));
	for(int i=0;i<m;i++){
		int u,v,c,d;
		cin >> u >> v >> c >> d;
		u--;
		v--;
		e[u].push_back({v,i,c,d});
		ez[u][v]=min(ez[u][v],c);
	}
	for(int i=0;i<n;i++){
		ez[i][i]=0;
	}
	vector<int> to[2];
	to[0].resize(n);
	to[1].resize(n);
	auto tmp=fw(ez);
	to[0]=tmp.fs;
	to[1]=tmp.sc;
	/*
	for(int i=0;i<n;i++){
		to[0][i]=dijk(i,n-1,2);
		to[1][i]=dijk(i,0,2);
	}
	*/
	int ans=0;
	ans+=dijk(0,n-1,0);
	ans+=dijk(n-1,0,1);
	/*
	for(int i=0;i<n;i++){
		cout << dz[0][i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << dz[1][i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << to[0][i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << to[1][i] << " ";
	}
	cout << "\n";
	cout << "\n";
	*/
	for(int i=0;i<n;i++){
		for(int j=0;j<e[i].size();j++){
			auto h=e[i][j];
			int yy=dz[0][n-1],kk=inf;
			int ff=0;
			if(dz[0][h.v]+h.c+h.d<=dz[0][i]){
				ff+=2;
				yy=min(yy,dz[0][h.v]+h.c+h.d+to[0][i]);
				//if(yy<dz[0][n-1]){
					if(p[1][h.v]==h.id){
						//e[i][j].c+=h.d;
						e[j].push_back({i,-1,h.c+h.d,0});
						kk=min(kk,yy+dijk(n-1,0,2));
						//e[i][j].c-=h.d;
						e[j].pop_back();
					}
					else{
						kk=min(kk,yy+dz[1][0]);
					}
				//}
			}
			yy=dz[1][0];
			if(dz[1][h.v]+h.c+h.d<=dz[1][i]){
				ff++;
				yy=min(yy,dz[1][h.v]+h.c+h.d+to[1][i]);
				
				//if(yy<dz[1][0]){
					if(p[0][h.v]==h.id){
						
						e[j].push_back({i,-1,h.c+h.d,0});
						//e[i][j].c+=h.d;
						kk=min(kk,yy+dijk(0,n-1,2));
						e[j].pop_back();
						//e[i][j].c-=h.d;
					}
					else{
						kk=min(kk,yy+dz[0][n-1]);
					}
				//}
			}
			if(ff==3){
				kk=min(kk,min(dz[0][n-1],dz[0][h.v]+h.c+h.d+to[0][i])+min(dz[1][0],dz[1][h.v]+h.c+h.d+to[1][i]));
			}
			ans=min(ans,kk);
		}
	}
	if(ans>=inf){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:113:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<eg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int j=0;j<e[i].size();j++){
      |               ~^~~~~~~~~~~~

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