Hello 2025 : E2. Another Exercise on Graphs (hard version)

本番中意外にすんなり解いてるな。
https://codeforces.com/contest/2057/problem/E2

問題

N点M辺の無向グラフが与えられる。
各辺には重みが設定されている。

以下のクエリに答えよ。

• 2点A,Bと整数値Kが与えられる。A→Bのあらゆるパスのうち、K番目に大きい重みの辺の最小値を答えよ。

解法

まず全辺使える場合の、重みを無視した全点間の距離をFloyd–Warshall法で求める。

重みX未満の辺のコストは0とみなし、残った辺のコストを1としたとき、2点A-B間のコストがK以上なら、クエリの解はK以上となる。
これを再現しよう。
辺を重みの小さい順に1個ずつコストを0にしながら、2点間のコストを削減していくとよい。

int T,N,M;
int Q;
int A[400*400+5],B[400*400+5],W[400*400+5];
int D[404][404];
int ret[404][404][404];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>Q;
		FOR(x,N) FOR(y,N) D[x][y]=(x==y)?0:1000;
		FOR(x,N) FOR(y,N) FOR(k,N+2) ret[x][y][k]=1<<30;
		vector<pair<int,int>> Es;
		FOR(i,M) {
			cin>>A[i]>>B[i]>>W[i];
			A[i]--;
			B[i]--;
			Es.push_back({W[i],i});
			D[A[i]][B[i]]=D[B[i]][A[i]]=1;
		}
		FOR(k,N) FOR(x,N) FOR(y,N) D[x][y]=min(D[x][y],D[x][k]+D[k][y]);
		
		sort(ALL(Es));
		FORR2(a,e,Es) {
			x=A[e],y=B[e];
			if(D[x][y]==0) continue;
			D[x][y]=D[y][x]=0;
			FOR(i,N) FOR(j,N) D[i][j]=min({D[i][j],D[i][x]+D[y][j],D[i][y]+D[x][j]});
			FOR(i,N) FOR(j,N) chmin(ret[i][j][D[i][j]+1],a);
		}
		FOR(x,N) FOR(y,N) FOR(k,N) ret[x][y][k+1]=min(ret[x][y][k+1],ret[x][y][k]);
		while(Q--) {
			cin>>x>>y>>k;
			x--,y--;
			cout<<ret[x][y][k]<<" ";
		}
		cout<<endl;
		
	}
}

まとめ

これは無事思いつけて良かったな。