Submission #1276940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276940		PieArmy	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	236 ms	6096 KiB

ho_t4

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll
int n,m;
pair<pair<int,int>,pair<int,int>>ed[50023];
vector<pair<ll,int>>git1,gel1,gitn,geln;
vector<int>h[223][223],o[223][223];

vector<pair<ll,int>> f(int bas,bool t){
	vector<bool>vis(n,false);
	vector<pair<ll,int>>dp(n,{2e15,2e15});
	dp[bas]={0,0};
	while(true){
		int pos=-1;
		for(int i=0;i<n;i++){
			if(vis[i])continue;
			if(pos==-1||dp[i].fr<dp[pos].fr)pos=i;
		}
		if(pos==-1)break;
		vis[pos]=true;
		for(int i=0;i<n;i++){
			if(vis[i])continue;
			vector<int>&v=(t?o:h)[pos][i];
			if(!v.size())continue;
			dp[i]=min(dp[i],{dp[pos].fr+ed[v.back()].sc.fr,v.back()});
		}
	}
	return dp;
}

int32_t main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c,d;cin>>a>>b>>c>>d;
		a--;b--;
		ed[i]={{a,b},{c,d}};
		h[a][b].pb(i);
		o[b][a].pb(i);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			sort(h[i][j].begin(),h[i][j].end(),[&](const int &x,const int &y){
				return ed[x].sc.fr>ed[y].sc.fr;
			});
			sort(o[i][j].begin(),o[i][j].end(),[&](const int &x,const int &y){
				return ed[x].sc.fr>ed[y].sc.fr;
			});
		}
	}
	git1=f(0,0);
	gel1=f(0,1);
	gitn=f(n-1,0);
	geln=f(n-1,1);
	ll ans=git1[n-1].fr+gitn[0].fr;
	for(int i=1;i<=m;i++){
		int a=ed[i].fr.fr,b=ed[i].fr.sc,c=ed[i].sc.fr,d=ed[i].sc.sc;
		ll res=d;
		if(git1[b].sc!=i&&geln[a].sc!=i){
			res+=min(git1[n-1].fr,git1[b].fr+geln[a].fr+c);
		}
		else{
			int x=0;
			if(h[a][b].back()==i){
				h[a][b].pop_back();
				o[b][a].pop_back();
				x+=1;
			}
			if(h[b][a].size()==0||ed[h[b][a].back()].sc.fr>c){
				h[b][a].pb(i);
				o[a][b].pb(i);
				x+=2;
			}
			res+=f(0,0)[n-1].fr;
			if(x&2){
				h[b][a].pop_back();
				o[a][b].pop_back();
			}
			if(x&1){
				h[a][b].pb(i);
				o[b][a].pb(i);
			}
		}
		if(gitn[b].sc!=i&&gel1[a].sc!=i){
			res+=min(gitn[0].fr,gitn[b].fr+gel1[a].fr+c);
		}
		else{
			int x=0;
			if(h[a][b].back()==i){
				h[a][b].pop_back();
				o[b][a].pop_back();
				x+=1;
			}
			if(h[b][a].size()==0||ed[h[b][a].back()].sc.fr>c){
				h[b][a].pb(i);
				o[a][b].pb(i);
				x+=2;
			}
			res+=f(n-1,0)[0].fr;
			if(x&2){
				h[b][a].pop_back();
				o[a][b].pop_back();
			}
			if(x&1){
				h[a][b].pb(i);
				o[b][a].pb(i);
			}
		}
		ans=min(ans,res);
	}
	if(ans>=2e15){
		cout<<-1<<endl;
	}
	else cout<<ans<<endl;
}

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