제출 #259013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259013		ttnhuy313	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	442 ms	5368 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll maxn=2e2+10, maxm=5e4+10, lg=21, mod=1e9+7, inf=1e18;
 
ll n,m,V[maxm],U[maxm],C[maxm],ans[maxm];
bool mk[maxn];
void dij(ll sr,vector<ll> adj[],ll dis[],ll par[]){
	for(int i=0;i<=n;i++) dis[i]=inf, par[i]=mk[i]=0;
	dis[sr]=0;
	while(1){
		ll v=0;
		for(int i=1;i<=n;i++)if(!mk[i] && dis[i]<dis[v]) v=i;
		if(!v) return;
		mk[v]=1;
		for(auto i:adj[v]){
			ll u=V[i]^U[i]^v;
			if(dis[v]+C[i]<dis[u]) dis[u]=dis[v]+C[par[u]=i];
		}
	}
}
 
ll dis[3][maxn],py[3][maxn];
vector<ll> g[maxn],rg[maxn],gg[maxn];
bool dd[maxm];
void solve(ll a,ll b){
	dij(a,g,dis[0],py[0]), dij(b,rg,dis[1],py[1]);
	ans[0]+=dis[0][b];
	memset(dd,0,sizeof(dd)); for(int i=1;i<=n;i++) dd[py[0][i]]=dd[py[1][i]]=1;
	for(int i=1;i<=m;i++){
		if(dis[0][U[i]]>=inf || dis[1][V[i]]>=inf){
			ans[i]+=inf;
			continue;
		}
		if(!dd[i]) ans[i]+=min(dis[0][b],dis[0][U[i]]+C[i]+dis[1][V[i]]);
		else{
			for(int i=1;i<=n;i++) gg[i].clear();
			for(int j=1;j<=m;j++)if(i!=j) gg[V[j]].pb(j);
			gg[U[i]].pb(i);
			dij(a,gg,dis[2],py[2]);
			ans[i]+=dis[2][b];
		}
	}
}
 
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	//memset(ans,69,sizeof(ans));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>V[i]>>U[i]>>C[i]>>ans[i];
		g[V[i]].pb(i), rg[U[i]].pb(i);
	}
	solve(1,n), solve(n,1);
	ll jj=inf;
	for(int i=0;i<=m;i++) jj=min(jj,ans[i]);
	cout<<(jj>=inf ? -1:jj);
	
	return 0;
}
 

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