CodeQUEEN 2025 決勝 : G - 全国ツアー

意外にコード量が増えた。
https://atcoder.jp/contests/codequeen2025-final-Public/tasks/codequeen2025_final_g

問題

N点M辺の連結無向グラフが与えられる。
各辺には長さが設定されている。
N点中K点のうち、4か所以上を経由しながら、頂点1→頂点Nに移動する最短経路長さを答えよ。
なお、頂点1と頂点NはK点に含まれる。

解法

頂点1とN以外には、残り(K-2)点中2点経由しなければならない。
もしそのような点をu,vの2点通る場合、解はmin(dist(1,u)+dist(u,v)+dist(v,N))となる。
dist(1,*)及びdist(*,N)はあらかじめ求めておく。

以下をダイクストラ法で求めよう。
dp(a) := 頂点1と、(K-2)点中のうちのいずれか1点を経由して点aに到達したとき、その経路長と、通過した頂点対の上位2位まで。
そうすればdist(1,u)+dist(u,a)かつu!=aとなるときの最短路がわかる。
aが(K-2)点に含まれるのであれば、そこにdist(a,N)を加えれば解の候補となる。

int N,M,K;
int A[202020];
vector<pair<int,int>> E[202020];
ll dp[2][202020];
pair<int,ll> dp2[202020][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,K) {
		cin>>x;
		A[x-1]=1;
	}
	A[0]=A[N-1]=0;
	FOR(i,M) {
		cin>>x>>y>>k;
		E[x-1].push_back({y-1,k});
		E[y-1].push_back({x-1,k});
	}
	FOR(i,N) dp[0][i]=dp[1][i]=1LL<<60;
	dp[0][0]=dp[1][N-1]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,0});
	Q.push({0,N+N-1});
	while(Q.size()) {
		ll co=-Q.top().first;
		int id=Q.top().second/N;
		int cur=Q.top().second%N;;
		Q.pop();
		if(dp[id][cur]!=co) continue;
		FORR2(e,c,E[cur]) if(chmin(dp[id][e],co+c)) Q.push({-dp[id][e],id*N+e});
	}
	
	FOR(i,N) {
		dp2[i][0]={0,1LL<<60};
		dp2[i][1]={0,1LL<<60};
		if(A[i]) {
			dp2[i][0]={i,dp[0][i]};
			Q.push({-dp[0][i],i});
		}
	}
	
	ll ret=1LL<<60;
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second%N;
		Q.pop();
		if(dp2[cur][0].second!=co&&dp2[cur][1].second!=co) continue;
		if(A[cur]) {
			if(dp2[cur][0].first!=cur) ret=min(ret,dp2[cur][0].second+dp[1][cur]);
			if(dp2[cur][1].first!=cur) ret=min(ret,dp2[cur][1].second+dp[1][cur]);
		}
		FOR(i,2) FORR2(e,c,E[cur]) {
			ll co2=dp2[cur][i].second+c;
			if(co2<dp2[e][0].second) {
				if(dp2[cur][i].first==dp2[e][0].first) {
					dp2[e][0].second=co2;
				}
				else {
					dp2[e][1]=dp2[e][0];
					dp2[e][0]={dp2[cur][i].first,co2};
				}
				Q.push({-co2,e});
			}
			else if(co2<dp2[e][1].second) {
				if(dp2[cur][i].first!=dp2[e][0].first) {
					dp2[e][1]={dp2[cur][i].first,co2};
					Q.push({-co2,e});
				}
			}
		}
	}
	
	cout<<ret<<endl;
	
}

まとめ

想定解とは多少異なるけど、上位2位まで持つ点は同じだね。