JOI 17 本選-定期券

問題

https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf

考察

重要な性質として、ある定期券のもとでの $U$ から $V$ への最短経路は、

$U$ $\rightarrow$ [定期券に含まれない区間] $\rightarrow$ [定期券に含まれる区間] $\rightarrow$ [定期券に含まれない区間] $\rightarrow$ $V$

のような構成になると言えます（各区間は $∅$ も認める）。
なぜなら、仮に [定期券に含まれる区間] が複数に分かれて存在している場合、その最初の区間の最初の駅、および最後の区間の最後の駅を定期券に含まれる区間のみで繋ぐことでより運賃が安くできるからです。
$N \leq 300$ の部分点については、[定期券に含まれる区間] の始点と終点を全探索することで解けます（ある 2 つの駅 $a$ と $b$ をこの順に通る $S$ から $T$ への最短経路、つまり適切な定期券が存在するかは、 $d_{ij}$ を $i$ と $j$ の距離として $d_{Sa} + d_{ab} + d_{bT} = d_{ST}$ となるかを見ることで判定できます）。
動的計画法を利用すると、さらに計算量を小さくすることができます。
$U$ からいくつかの駅を経由して定期券の区間に合流し、そのまま $S$ から遠ざかるように進んで適当なところで分かれ $V$ を目指すケースの最適値をまず考えます。逆（定期券の区間に合流したあと、 $S$ に近づくように進む場合）も同様に計算できます。
以下、 $j$ を含むような $S$ から $i$ への最短経路が存在するとき、 $j$ を $i$ の 上流の駅 と呼びます。 $i$ の上流の駅全体を集合 $K_i$ とします。

$dp_{0i} := min_{j \in K_i}\{d_{Uj}\}$
$dp_{1i} := min_{j \in K_i}\{$ $j$ で定期券区間を分離して $V$ を目指したときの（合流するまでも含む）運賃の最小 $\}$

のように定めます。また駅 $i$ と接する駅のなかで

$d_{Sj} + d_{ji} = d_{Si}$

を満たす $j$ を、 $i$ の すぐ上の駅 と呼ぶことにします。逆に、任意の $S$ から $i$ への最短経路は、上の式のように適当なすぐ上の駅を経由する形に分解できます。
そして $i$ の上流の駅は、それ自身を除けば何らかのすぐ上の駅の上流の駅でもあります。
これを踏まえると、 $dp_{0i}$ および $dp_{1i}$ は、 $i$ のすぐ上の駅全体の集合を $L_i$ とすると、

$dp_{0i} = min(d_{Ui},\,min_{j \in L_i}\{dp_{0j}\})$
$dp_{1i} = min(dp_{0i} + d_{iV},\,min_{j \in L_i}\{dp_{1j}\})$

のように更新ができます。配列の更新は $S$ に近い駅から行っていくことで、うまく動きます。以上より最適値は $dp_{1T}$ となる……ように見えますが、実はこの動的計画法では、定期券の区間に一度も合流しないケース（入力例 2 のようなケース）を考慮していないため、 $min(dp_{1T},\,d_{UV})$ が本当の求める値になります。

コード

ll N,M,S,T,U,V;
vector<P> graph[100010];
ll fromU[100010];
ll fromV[100010];
P dp1[100010];
P dp2[100010];

void dijkstra(ll s, vector<ll>& d) {
	REP(i,N) d[i]=INF*INF;
	d[s]=0;
	priority_queue<P,vector<P>,greater<P>> q;
	q.push(P(0,s));
	while(!q.empty()) {
		ll cost=q.top().first;
		ll p=q.top().second;
		q.pop();
		if(d[p]!=cost) continue;
		REP(i,(ll)graph[p].size()) {
			ll adj=graph[p][i].first;
			if(d[adj]>d[p]+graph[p][i].second) {
				d[adj]=d[p]+graph[p][i].second;
				q.push(P(d[adj],adj));
			}
		}
	}
	return;
}

ll dp() {
	vector<ll> d(N);
	REP(i,N) d[i]=INF*INF;
	d[S]=0;
	priority_queue<P,vector<P>,greater<P>> q;
	q.push(P(0,S));
	while(!q.empty()) {
		ll cost=q.top().first;
		ll p=q.top().second;
		q.pop();
		if(d[p]!=cost) continue;
		REP(i,(ll)graph[p].size()) {
			ll adj=graph[p][i].first;
			if(d[adj]+graph[p][i].second==d[p]) {
				dp1[p].first=min(dp1[adj].first,dp1[p].first);
				dp2[p].first=min(dp2[adj].first,dp2[p].first);
			}
		}
		dp1[p].second=dp1[p].first+fromV[p];
		dp2[p].second=dp2[p].first+fromU[p];
		REP(i,(ll)graph[p].size()) {
			ll adj=graph[p][i].first;
			if(d[adj]+graph[p][i].second==d[p]) {
				dp1[p].second=min(dp1[adj].second,dp1[p].second);
				dp2[p].second=min(dp2[adj].second,dp2[p].second);
			}
			if(d[adj]>d[p]+graph[p][i].second) {
				d[adj]=d[p]+graph[p][i].second;
				q.push(P(d[adj],adj));
			}
		}
	}
	ll ret=min(dp1[T].second,dp2[T].second);
	return ret;
}

int main() {
	cin>>N>>M>>S>>T>>U>>V;
	S--; T--; U--; V--;
	graph.resize(N); dp1.resize(N); dp2.resize(N);
	fromU.resize(N); fromV.resize(N);
	REP(i,M) {
		ll A,B,C;
		cin>>A>>B>>C;
		A--; B--;
		graph[A].pb(P(B,C));
		graph[B].pb(P(A,C));
	}
	dijkstra(U,fromU); dijkstra(V,fromV);
	REP(i,N) {
		dp1[i].first=fromU[i];
		dp2[i].first=fromV[i];
	}
	cout<<min(fromU[V],dp())<<endl;
}