Submission #537159

#	Time	Username	Problem	Language	Result	Execution time	Memory
537159		alvingogo	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1086 ms	4192 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 int inf=4e18;
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>,vector<pair<int,int> >,greater<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;
	}
	assert(dis[y]<=inf);
	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,-1);
	p[1].resize(n,-1);
	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+1,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;
	int ans=inf;
	ans=min(inf,dijk(0,n-1,0)+dijk(n-1,0,1));
	for(int i=0;i<n;i++){
		for(int j=0;j<e[i].size();j++){
			auto h=e[i][j];
			e[h.v].push_back({i,-1,h.c+h.d,-1});
			e[i][j].c+=2*inf;
			ans=min(ans,dijk(0,n-1,2)+dijk(n-1,0,2));
			e[i][j].c-=2*inf;
			auto y=e[h.v].back();
			assert(y.v==i && y.id==-1 && y.c==h.c+h.d && y.d==-1);
			e[h.v].pop_back();
		}
	}
	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:88:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<eg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   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