yukicoder : No.1607 Kth Maximum Card

これも典型寄り？
https://yukicoder.me/problems/no/1607

問題

各辺にパラメータが振られた無向グラフが与えられる。
頂点1から頂点Nに辺をたどって移動したい。その際、同じ辺を複数回通っても良い。

通った辺のパラメータを降順に並べたとき、K番目に来る値の最小値を求めよ。

解法

「v以上のパラメータの辺をK回以内使って、頂点Nに移動できるか？」と言い換えると二分探索+01BFSに持ち込める。

int N,M,K;
vector<pair<int,int>> E[202020];
int dp[202020];
int can(int v) {
	int i;
	FOR(i,N) dp[i]=1<<20;
	dp[0]=0;
	deque<int> Q;
	Q.push_back(0);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop_front();
		FORR2(e,c,E[cur]) {
			if(c<v) {
				if(dp[e]>dp[cur]) {
					dp[e]=dp[cur];
					Q.push_front(e);
				}
			}
			else {
				if(dp[e]>dp[cur]+1) {
					dp[e]=dp[cur]+1;
					Q.push_back(e);
				}
			}
		}
		
	}
	return dp[N-1];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y>>k;
		E[x-1].push_back({y-1,k});
		E[y-1].push_back({x-1,k});
	}
	int mi=1<<20;
	for(i=19;i>=0;i--) if(can(mi-(1<<i))<K) mi-=1<<i;
	cout<<mi-1<<endl;
}

まとめ

これも思いつけば単純な問題。