제출 #227416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
227416		dvdg6566	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	1372 ms	51612 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(Z[mp(n,v.f)])w=d;
			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';
}
void doo(){
	dijkstra(X);
	ans=min(ans,d1[Y]);
	// dijkstra(Y);
	// ans=min(ans,d1[X]);
}

int main(){
	cin>>N>>M>>S>>T>>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];
	assert(tar==d1[S]);
	for (auto x:E){
		ll a=x.s.f;
		ll b=x.s.s;
		ll w=x.f;
		ll gay=0;
		if (d1[a]+w+d2[b]==tar){
			gay=1;
			useful.pb(b,a);
		}
		if(d1[b]+w+d2[a]==tar){
			if(gay)assert(0);
			useful.pb(a,b);
		}
	}
	for (auto i:useful)Z[mp(i.f,i.s)]=1;
	doo();
	Z.clear();
	for (auto i:useful)Z[mp(i.s,i.f)]=1;
	doo();
	cout<<ans<<'\n';
}

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