Submission #545216

#	Time	Username	Problem	Language	Result	Execution time	Memory
545216		inluminas	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	46 ms	9496 KiB

ho_t4

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const ll lmt=1e5+10;
ll E[lmt],to[lmt],n,m,dis2[lmt];
bool block[lmt];
vector<array<ll,3>>adj[lmt];

void dij(ll x){
	for(ll i=1;i<=n;i++){
		dis2[i]=1e16;
		to[i]=E[i]=0;
	}
	dis2[x]=0;
	set<pair<ll,ll>>q;
	q.insert({0,x});
	while(!q.empty()){
		auto it=q.begin();
		ll val=(*it).first,u=(*it).second;
		q.erase(it);
		if(dis2[u]<val) continue;
		for(auto z:adj[u]){
			ll w=z[0],v=z[1],idx=z[2];
			if(block[idx]) continue;
			if(dis2[v]>dis2[u]+w){
				dis2[v]=dis2[u]+w,to[v]=u,E[v]=idx;
				q.insert({dis2[v],v});
			}
		}
	}
	return;
}

int main(){
	fastio;

	cin>>n>>m;

	ll dis[n+1][n+1];

	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=n;j++) dis[i][j]=1e16;
		dis[i][i]=0;
	}

	vector<array<ll,4>>e;

	for(ll i=1;i<=m;i++){
		ll u,v,c,d;
		cin>>u>>v>>c>>d;
		e.push_back({u,v,c,d});
		dis[u][v]=min(dis[u][v],c);
		adj[u].push_back({c,v,i});
	}

	for(ll k=1;k<=n;k++){
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}

	ll ans=dis[1][n]+dis[n][1];

	dij(1);
	ll x=n;
	map<ll,bool>used;

	if(dis2[n]<1e16){
		while(x>1){
			used[E[x]]=1,x=to[x];
		}
	}

	x=1;
	dij(n);

	if(dis2[1]<1e16){
		while(x<n){
			used[E[x]]=1,x=to[x];
		}
	}

	for(ll i=1;i<=m;i++){
		if(used[i]) continue;

		ll u=e[i-1][0],v=e[i-1][1],c=e[i-1][2],d=e[i-1][3];

		ans=min(ans,dis[1][n]+dis[n][v]+c+d+dis[u][1]);
		ans=min(ans,dis[1][v]+c+d+dis[u][n]+dis[n][1]);
		ans=min(ans,dis[1][v]+c+d+dis[u][n]+dis[n][v]+c+d+dis[u][1]);
	}

	ll last=m;

	for(ll i=1;i<=m;i++){
		if(!used[i]) continue;

		ll u=e[i-1][0],v=e[i-1][1],c=e[i-1][2],d=e[i-1][3];

		block[i]=1;

		adj[v].push_back({c+d,u,++last});

		ll res=0;
		dij(1);
		res+=dis2[n];
		dij(n);
		res+=dis2[1];

		ans=min(ans,res);

		block[i]=0;

		adj[v].pop_back();
	}

	cout<<(ans>=1e16?-1:ans)<<endl;
	return 0;
}

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