제출 #321547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321547		YJU	Olympic Bus (JOI20_ho_t4)	C++14	21 / 100	66 ms	8908 KiB

ho_t4

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e2+5;
const ll M=5e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<58);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,dis[N][N],dist[N][N],Front[N][N],x,y,c[M],d[M],ans1[M],vis[M],ans,DIS[N][N],ans2[M];
vector<ll> lis,nd;
pll ed[M];


int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,n)REP1(j,n)dis[i][j]=(i==j?0LL:INF);
	REP1(i,m){
		cin>>ed[i].X>>ed[i].Y>>c[i]>>d[i];
		if(dis[ed[i].X][ed[i].Y]>c[i]){
			Front[ed[i].X][ed[i].Y]=i;
			dis[ed[i].X][ed[i].Y]=c[i];
		}
	}
	REP1(k,n)REP1(i,n)REP1(j,n){
		if(dis[i][k]+dis[k][j]<dis[i][j]){
			dis[i][j]=dis[i][k]+dis[k][j];
			Front[i][j]=Front[i][k];
		}
	}
	ans=dis[1][n]+dis[n][1];
	
	x=1;nd.pb(x);
	while(Front[x][n]){
		vis[Front[x][n]]=1;
		lis.pb(Front[x][n]);
		x=ed[Front[x][n]].Y;
		nd.pb(x);
	}
	
	REP1(i,n)REP1(j,n)dist[i][j]=(i==j?0:INF);
	REP1(i,m){
		if(!vis[i]){
			ans1[i]=min(dis[1][n],dis[1][ed[i].Y]+c[i]+dis[ed[i].X][n]);
			dist[ed[i].X][ed[i].Y]=min(dist[ed[i].X][ed[i].Y],c[i]);
		}
	}
	REP1(k,n)REP1(i,n)REP1(j,n)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	
	
	for(ll id:lis){
		for(ll i=SZ(nd)-1,suf=INF;;i--){
			suf=min(suf,dist[nd[i]][ed[id].Y]);
			DIS[nd[i]][ed[id].Y]=(nd[i]==ed[id].Y?0:suf);
			suf+=dis[nd[i-1]][nd[i]];
			if(nd[i]==ed[id].Y)break;
		}
		for(ll i=0;;i++){
			for(ll j=SZ(nd)-1;;j--){
				DIS[nd[i]][n]=dist[nd[i]][nd[j]]+dis[nd[j]][n];
				if(nd[j]==ed[id].Y)break;
			}
			if(nd[i]==ed[id].X)break;
		}
		for(ll i=0;;i++){
			for(ll j=SZ(nd)-1;;j--){
				ans1[id]=min(dis[1][nd[i]]+dist[nd[i]][nd[j]]+dis[nd[j]][n],dis[1][nd[i]]+dist[nd[i]][nd[j]]+DIS[nd[j]][ed[i].Y]+c[id]+DIS[ed[i].X][n]);
				if(nd[j]==ed[id].Y)break;
			}
			if(nd[i]==ed[id].X)break;
		}
	}
	
	lis.clear();nd.clear();memset(vis,0,sizeof(vis));
	
	x=n;nd.pb(x);
	while(Front[x][1]){
		vis[Front[x][1]]=1;
		lis.pb(Front[x][1]);
		x=ed[Front[x][1]].Y;
		nd.pb(x);
	}
	
	REP1(i,n)REP1(j,n)dist[i][j]=(i==j?0:INF);
	REP1(i,m){
		if(!vis[i]){
			ans2[i]=min(dis[n][1],dis[n][ed[i].Y]+c[i]+dis[ed[i].X][1]);
			dist[ed[i].X][ed[i].Y]=min(dist[ed[i].X][ed[i].Y],c[i]);
		}
	}
	REP1(k,n)REP1(i,n)REP1(j,n)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	
	for(ll id:lis){
		for(ll i=SZ(nd)-1,suf=INF;;i--){
			suf=min(suf,dist[nd[i]][ed[id].Y]);
			DIS[nd[i]][ed[id].Y]=(nd[i]==ed[id].Y?0:suf);
			suf+=dis[nd[i-1]][nd[i]];
			if(nd[i]==ed[id].Y)break;
		}
		for(ll i=0;;i++){
			for(ll j=SZ(nd)-1;;j--){
				DIS[nd[i]][1]=dist[nd[i]][nd[j]]+dis[nd[j]][1];
				if(nd[j]==ed[id].Y)break;
			}
			if(nd[i]==ed[id].X)break;
		}
		for(ll i=0;;i++){
			for(ll j=SZ(nd)-1;;j--){
				ans2[id]=min(dis[n][nd[i]]+dist[nd[i]][nd[j]]+dis[nd[j]][1],dis[n][nd[i]]+dist[nd[i]][nd[j]]+DIS[nd[j]][ed[i].Y]+c[id]+DIS[ed[i].X][1]);
				if(nd[j]==ed[id].Y)break;
			}
			if(nd[i]==ed[id].X)break;
		}
	}
	
	REP1(i,m)ans=min(ans,ans1[i]+ans2[i]+d[i]);
	cout<<(ans>=INF?-1:ans)<<"\n";
	
	return 0;
}

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