Submission #283416

#	Time	Username	Problem	Language	Result	Execution time	Memory
283416		YJU	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	590 ms	34676 KiB

commuter_pass

#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=2e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#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,S,T,U,V,x,y,w,dis,ans;
vector<pll> v[N];
vector<ll> nv[N];
ll dv[N],du[N],ds[N],uans[N],vans[N],tans[N];
ll dg[N];
priority_queue<pll,vector<pll>,greater<pll> > pq;
queue<ll> Q;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);	
	cin>>n>>m>>S>>T>>U>>V;
	REP(i,m){
		cin>>x>>y>>w;
		v[x].pb(mp(y,w));v[y].pb(mp(x,w));
	}
	//prepare
	REP1(i,n){
		dv[i]=du[i]=ds[i]=uans[i]=vans[i]=tans[i]=INF;
	}
	//
	//build dis from U,V,S
	pq.push(mp(0,U));
	while(SZ(pq)){
		x=pq.top().Y;dis=pq.top().X;
		pq.pop();
		if(dis>=du[x])continue;
		du[x]=dis;
		for(auto i:v[x])pq.push(mp(dis+i.Y,i.X));
	}
	pq.push(mp(0,V));
	while(SZ(pq)){
		x=pq.top().Y;dis=pq.top().X;
		pq.pop();
		if(dis>=dv[x])continue;
		dv[x]=dis;
		for(auto i:v[x])pq.push(mp(dis+i.Y,i.X));
	}
	pq.push(mp(0,S));
	while(SZ(pq)){
		x=pq.top().Y;dis=pq.top().X;
		pq.pop();
		if(dis>=ds[x])continue;
		ds[x]=dis;
		for(auto i:v[x])pq.push(mp(dis+i.Y,i.X));
	}
	//end
	REP1(i,n){
		for(auto j:v[i]){
			if(ds[j.X]==ds[i]+j.Y){
				nv[i].pb(j.X);++dg[j.X];
			}
		}
	}
	Q.push(S);
	while(SZ(Q)){
		x=Q.front();
		Q.pop();
		tans[x]=min(tans[x],min(uans[x]+dv[x],vans[x]+du[x]));
		for(auto i:nv[x]){
			uans[i]=min(uans[i],min(uans[x],du[x]));
			vans[i]=min(vans[i],min(vans[x],dv[x]));
			tans[i]=min(tans[i],tans[x]);
			--dg[i];
			if(dg[i]==0)Q.push(i);
		}
	}
	/*REP1(i,n){
		cout<<i<<" "<<(uans[i]>=INF?-1:uans[i])<<" "<<(vans[i]>=INF?-1:vans[i])<<"\n";
	}*/
	ans=tans[T];
	REP1(i,n)ans=min(ans,du[i]+dv[i]);
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45