Submission #227427

#	Time	Username	Problem	Language	Result	Execution time	Memory
227427		dvdg6566	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	842 ms	40232 KiB

commuter_pass

#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 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 = 200100;
const ll INF = 1e18;
const ll MOD = 1e9+7;

typedef pair<ll,pi> pip;
vector<pip> E;
vpi V[MAXN];
ll d1[MAXN];
ll d2[MAXN];
ll N,M,a,b,w;
ll S,T,X,Y;
priority_queue<pi,vpi,greater<pi>>pq;
map<pi,ll> Z;
vpi useful;
ll ans=INF;

void dijkstra(int rt){
	memset(d1,-1,sizeof(d1));
	d1[rt]=0;
	pq.push(mp(0,rt));
	while (SZ(pq)){
		ll n = pq.top().s;
		ll d =pq.top().f;
		pq.pop();
		if (d1[n]!=d)continue;
		for (auto v:V[n]){
			ll w=d+v.s; 
			if (d1[v.f]!=-1&&d1[v.f]<=w)continue;
			d1[v.f]=w;
			pq.push(mp(w,v.f));
		}
	}
	// cout<<"Distances from node "<<rt<<'\n';
	// for (int i=1;i<=N;++i)cout<<d1[i]<<' ';cout<<'\n';
}

ll D[300100];
void dijkstra2(int rt){
	memset(D,-1,sizeof(D));
	D[rt]=0;
	pq.push(mp(0,rt));
	while (SZ(pq)){
		ll n = pq.top().s;
		ll d =pq.top().f;
		pq.pop();
		if (D[n]!=d)continue;
		ll b=((n-1)/N);n-=b*N;
		// cerr<<b<<' '<<n<<' '<<d<<'\n';
		if (b==0){ // Hvae not gone anywhere
			for (auto v:V[n]){
				ll w=d+v.s;
				ll c=v.f;
				if(v.s==0)c=N+v.f;
				if (D[c]!=-1&&D[c]<=w)continue;
				D[c]=w;
				pq.push(mp(w,c));
			}
		}else if (b==1){
			for (auto v:V[n]){
				ll w=d+v.s;
				ll c=v.f+2*N;
				if(v.s==0){c=N+v.f;}
				if (D[c]!=-1&&D[c]<=w)continue;
				D[c]=w;
				pq.push(mp(w,c));
			}
		}else{
			for (auto v:V[n]){
				ll w=d+v.s;
				ll c=v.f+2*N;
				if (v.s==0)continue;
				if (D[c]!=-1&&D[c]<=w)continue;
				D[c]=w;
				pq.push(mp(w,c));
			}
		}
	}
	for (int i=0;i<3;++i)if(D[i*N+Y]!=-1)ans=min(ans,D[i*N+Y]);
	// cout<<'\n';
}

int main(){
	cin>>N>>M>>S>>T>>X>>Y;
	swap(X,Y);
	for (int i=0;i<M;++i){
		cin>>a>>b>>w;
		E.pb(w, mp(a,b));
		V[a].pb(b,w);
		V[b].pb(a,w);
	}
	dijkstra(S);
	for (int i=1;i<=N;++i)d2[i]=d1[i];
	dijkstra(T);
	// d2 is distance from S, d1 is distance from T
	ll tar = d2[T];
	for (auto x:E){
		ll a=x.s.f;
		ll b=x.s.s;
		ll w=x.f;
		if (d1[a]+w+d2[b]==tar){
			useful.pb(b,a);
		}else if(d1[b]+w+d2[a]==tar){
			useful.pb(a,b);
		}
	}
	for (auto i:useful)V[i.f].pb(i.s,0);
	dijkstra2(X);
	for (auto i:useful)V[i.f].pop_back();
	for (auto i:useful)V[i.s].pb(i.f,0);
	dijkstra2(X);
	cout<<ans<<'\n';
}

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