Submission #545208

#	Time	Username	Problem	Language	Result	Execution time	Memory
545208		inluminas	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	129 ms	7544 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=201;
vector<array<ll,3>>adj[lmt];
ll dis[lmt][lmt][2],node[lmt][lmt],e[lmt][lmt];

int main(){
	fastio;

	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=n;j++) for(ll k=0;k<2;k++) dis[i][j][k]=1e17;
	}
	vector<array<ll,3>>inv;
	for(ll i=1;i<=m;i++){
		ll u,v,c,d;
		cin>>u>>v>>c>>d;
		inv.push_back({v,u,c+d});
		adj[u].push_back({c,v,i});
	}
	for(ll x=1;x<=n;x++){
		dis[x][x][0]=0;
		set<array<ll,3>>q;
		q.insert({0,x,0});
		while(!q.empty()){
			auto it=q.begin();
			ll val=(*it)[0],u=(*it)[1],ver=(*it)[2];
			q.erase(it);

			if(dis[x][u][ver]<val) continue;

			for(auto p:adj[u]){
				ll w=p[0],v=p[1],idx=p[2];
				if(dis[x][v][0]>dis[x][u][ver]+w){
					dis[x][v][0]=dis[x][u][ver]+w,node[x][v]=u,e[x][v]=idx;
					q.insert({dis[x][v][0],v,0});
				}else if(dis[x][v][1]>dis[x][u][ver]+w){
					dis[x][v][1]=dis[x][u][ver]+w;
					q.insert({dis[x][v][1],v,1});
				}
			}
		}
	}

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

	//cout<<dis[1][n][0]<<" "<<dis[n][1][0]<<endl;

	if(dis[1][n][0]<1e17){
		ll x=n;
		map<ll,bool>used;
		while(x>1){
			used[e[1][x]]=1,x=node[1][x];
		}
		for(ll i=1;i<=m;i++){
			ll u=inv[i-1][0],v=inv[i-1][1],val=inv[i-1][2],res;
			if(used[i]){
				res=dis[1][v][0]+dis[u][n][0]+dis[v][u][1]+dis[n][u][0]+val+dis[v][1][0];
			}else{
				res=dis[1][n][0]+dis[n][u][0]+val+dis[v][1][0];
			}
			ans=min(ans,res);
		}
	}

	if(dis[n][1][0]<1e17){
		ll x=1;
		map<ll,bool>used;
		while(x<n){
			used[e[n][x]]=1,x=node[n][x];
		}
		for(ll i=1;i<=m;i++){
			ll u=inv[i-1][0],v=inv[i-1][1],val=inv[i-1][2],res;
			if(used[i]){
				res=dis[n][v][0]+dis[u][1][0]+dis[v][u][1]+dis[1][u][0]+val+dis[v][n][0];
			}else{
				res=dis[n][1][0]+dis[1][u][0]+val+dis[v][n][0];
			}
			ans=min(ans,res);
		}
	}

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

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