Submission #228514

#	Time	Username	Problem	Language	Result	Execution time	Memory
228514		dvdg6566	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	650 ms	6756 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define emp emplace
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 210;
const ll MAXE = 50100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

typedef pair<pi,pi> pp;
typedef pair<ll,pi> pip;
vector<vector<pip>> V,O,S;
vi f1,fn,b1,bn;
ll N,E,a,b,w,r;
ll U[MAXE];
ll l[MAXN];
vector<pp> Edge;
priority_queue<pi,vpi,greater<pi>>pq;
ll BLOCK=-1;

void dijkstra(ll x, vector<vector<pip>> &A, vi &D){
	// cout<<x<<'\n';
	D.resize(N+1);
	for(ll i=1;i<=N;++i)D[i]=INF;
	D[x]=0;
	pq.emp(0,x);
	while(SZ(pq)){
		pi t=pq.top();pq.pop();
		ll n=t.s;ll d=t.f;
		if(D[n]>d)continue;
		if(n!=x)U[l[n]]=1;
		for(auto t:A[n]){
			ll c=t.f;ll nd=d+t.s.f;
			if(nd>=D[c])continue;
			if(t.s.s==BLOCK)continue;
			D[c]=nd;
			l[c]=t.s.s;
			pq.emp(nd,c);
		}
	}
}

int main(){
	cin>>N>>E;
	V.resize(N+1);O.resize(N+1);S.resize(N+1);
	for (ll i=0;i<E;++i){
		cin>>a>>b>>w>>r;
		V[a].pb(b, mp(w,i));
		O[b].pb(a, mp(w,i));
		Edge.pb(mp(a,b),mp(w,r));
	}
	dijkstra(1,V,f1);
	dijkstra(N,V,fn);
	dijkstra(1,O,b1);
	dijkstra(N,O,bn);
	// for (ll i=0;i<E;++i)cout<<U[i]<<' ';cout<<'\n';
	ll ans=f1[N]+bn[1];
	// cout<<ans<<'\n';
	for(ll i=0;i<E;++i)if(U[i]){
		S[Edge[i].f.f].pb(Edge[i].f.s, mp(Edge[i].s.f, i));
	}
	for(ll i=0;i<E;++i)if(!U[i]){
		ll a=Edge[i].f.f;ll b=Edge[i].f.s;ll w=Edge[i].s.f;
		ll forward=min(f1[N],f1[b]+w+bn[a]);
		ll back=min(fn[1],fn[b]+w+b1[a]);
		ll tw=Edge[i].s.s+forward+back;
		ans=min(ans,tw);
	}
	for (ll i=0;i<E;++i)if(U[i]){
		ll a=Edge[i].f.f;ll b=Edge[i].f.s;ll w=Edge[i].s.f;
		BLOCK=i;
		vi d1,d2;
		V[b].pb(a,mp(w,0));
		dijkstra(1,V,d1);dijkstra(N,V,d2);
		ll tw=Edge[i].s.s+d1[N]+d2[1];
		// cout<<tw<<'\n';
		ans=min(ans,tw);
		V[b].pop_back();
	}
	if(ans>=INF)cout<<-1;
	else cout<<ans;
}

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