AtCoder ABC #308 (CodeQUEEN 2023 予選) : Ex - Make Q

なるほど。
https://atcoder.jp/contests/abc308/tasks/abc308_h

問題

無向グラフが与えられる。
各辺にはコストが設定されている。

この辺の部分集合が、アルファベットのQを成すようにしたい。
すなわち、単純サイクルが1つあり、サイクル上の点から、1本サイクル外の点につながる辺を加えたものである。
条件を満たす辺の集合のコストの総和の最小値を求めよ。

解法

サイクル上の点であって、サイクル外の点に辺を伸ばす点vを総当たりしよう。
まず、vを含む最短の単純サイクルを求めよう。
これはvを始点とする最短経路木を作る。

次に、最短経路木上で、同じvの隣接点を通らないような2点を選び、その間に辺があるならそれを結べば最短のサイクルの候補となる。
最短サイクルを1つ求めたら、vからサイクル外の点への辺を総当たりすればよい。

場合によっては、最短サイクル中に辺を追加するより、別のサイクルに対しvから延びる最短サイクルの辺を追加した方がいい可能性がある。
これは、最短サイクル中でvから延びる2辺をそれぞれいったん削除することで、その辺を含まない別の最短サイクルを再度探索してみればよい。

int N,M;
ll E[303][303];

ll dp[303];
int L[303],pre[3030];

vector<ll> hoge(int i) {
	int j,e;
	FOR(j,N) dp[j]=1LL<<30, L[j]=-1, pre[j]=-1;
	priority_queue<pair<ll,int>> Q;
	dp[i]=0;
	L[i]=i;
	pre[i]=i;
	Q.push({0,i});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(dp[cur]!=co) continue;
		FOR(e,N) if(dp[e]>co+E[cur][e]) {
			dp[e]=co+E[cur][e];
			pre[e]=cur;
			if(cur==i) L[e]=e;
			else L[e]=L[cur];
			Q.push({-dp[e],e});
		}
	}

	int ta=-1,tb=-1;
	ll mco=1LL<<30;
	int a,b;
	FOR(a,N) if(i!=a&&dp[a]<1LL<<30) {
		FOR(b,N) if(L[a]!=L[b]) {
			if(pre[a]==b||pre[b]==a) continue;
			ll co=dp[a]+dp[b]+E[a][b];
			if(co<mco) {
				mco=co;
				ta=a;
				tb=b;
			}
		}
	}
	return {mco,ta,tb};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) E[x][y]=1LL<<30;
	FOR(i,M) {
		cin>>x>>y>>k;
		E[x-1][y-1]=E[y-1][x-1]=k;
	}
	ll ret=1LL<<60;
	
	FOR(i,N) {
		vector<ll> V=hoge(i);
		ll mco=V[0];
		int ta=V[1],tb=V[2];
		if(ta>=0) {
			set<int> S;
			
			if(tb==i) {
				x=L[ta];
				y=tb;
			}
			else {
				x=L[ta];
				y=L[tb];
			}
			
			while(ta!=i) S.insert(ta), ta=pre[ta];
			while(tb!=i) S.insert(tb), tb=pre[tb];
			FOR(j,N) if(S.count(j)==0) ret=min(ret,mco+E[i][j]);
			
			k=E[i][x];
			E[i][x]=E[x][i]=1<<30;
			auto W=hoge(i);
			ret=min(ret,W[0]+k);
			E[i][x]=E[x][i]=k;
			
			k=E[i][y];
			E[i][y]=E[y][i]=1<<30;
			W=hoge(i);
			ret=min(ret,W[0]+k);
			E[i][y]=E[y][i]=k;
			
		}
		
	}
	
	if(ret>=1LL<<30) ret=-1;
	cout<<ret<<endl;
}

まとめ

このサイクルの作り方知らなかったな。