pku 3662 Telephone Lines

問題概要:頂点数N(<=1000),辺の数P(<=10000)の重み(1以上1e6以下)付き無向グラフが与えられる 頂点1からNへの経路で、使った辺のうち好きなK本の重みを0にしていい時、使った辺のうち最も重い辺の最小値を答えよ

解答:にぶたん+01dijkstra
"重さwまでの辺を使っていいことにした時、1からNへ残りK本付け加えて辿り着けるなら答えはw以下"なので、wでにぶたん

実は01dijkstra書いたことなかった
どちらかというとdijkstraというよりかbfsだが、

if(d[e.to]>d[v]+e.cost)

の部分にdijkstraっぽさが残っている(これがないとこの図のとき死ぬ)

コード:

#include <cstdio>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define all(c) (c).begin(),(c).end()
struct edge{int to,cost;};
vector<edge> G[1000];
deque<int> deq;
int a[10000],b[10000],l[10000],d[1000];
int main(){
	int n,p,k;
	scanf("%d%d%d",&n,&p,&k);
	rep(i,p){
		scanf("%d%d%d",a+i,b+i,l+i);
		a[i]--,b[i]--;
	}
	int ub=1e6+1,lb=-1;
	while(ub-lb>1){
		int m=(ub+lb)/2;
		rep(i,n) G[i].clear(),d[i]=1e8;
		rep(i,p){
			int cost=1;
			if(l[i]<=m) cost=0;
			G[a[i]].push_back({b[i],cost});
			G[b[i]].push_back({a[i],cost});
		}
		deq.clear();
		deq.push_front(0);
		d[0]=0;
		while(!deq.empty()){
			int v=deq.front();
			deq.pop_front();
			rep(i,G[v].size()){
				edge e=G[v][i];
				if(d[e.to]>d[v]+e.cost){
					if(e.cost==1){
						deq.push_back(e.to);
						d[e.to]=d[v]+1;
					}
					if(e.cost==0){
						deq.push_front(e.to);
						d[e.to]=d[v];
					}
				}
			}
		}
		if(d[n-1]<=k) ub=m;
		else lb=m;
	}
	if(ub==1e6+1) ub=-1;
	printf("%d\n",ub);
	return 0;
}