3662 Telephone Lines

問題概要

N個のノードとM個の辺からなる無向グラフで、1番のノードからN番のノードまで行くパスを作りたい。
好きなK本の辺は無料にしてもらえて、残りの辺のうち最大の長さがパスのコストになる。

パスのコストの最小値を求めよ。

解法

問題文がk種類の長さの辺を無料にするように読める気が……

長さlまでの辺の重みを0、lより大きい辺の重みを1にしたグラフで1番のノードからN番のノードまで最短で行く問題はダイクストラ法により解ける。
k本の辺が無料になるので、この最短路がk以下であれば、元の問題はl以下のコストのパスが存在することがわかる。

したがってlを二分探索で動かせばよい。

ソースコード

ダイクストラの辺の重みが全て0,1なので線形時間で出来ることを利用してみた。
ついでに辺にvectorを使わずにやってみたんだけど、実行時間が他の人より遅い……何故……

int n,m,k;
int e[1000],ne;
int t[20001],c[20001],nx[20001];

bool ok(int lim)
{
	deque<pi> Q; bool v[1000]={0};
	Q.pb(mp(0,0));
	while(!Q.empty())
	{
		int cc=Q.front().first,cur=Q.front().second; Q.pop_front();
		if(v[cur])continue;
		v[cur]=1; if(cur==n-1)return cc<=k;
		for(int i=e[cur];i;i=nx[i])if(!v[t[i]])
		{
			if(c[i]<=lim)Q.push_front(mp(cc,t[i]));
			else Q.pb(mp(cc+1,t[i]));
		}
	}
	return 0;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	ne=1;
	rep(i,m)
	{
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d); a--; b--;
		nx[ne]=e[a];
		e[a]=ne; t[ne]=b; c[ne++]=d;
		nx[ne]=e[b];
		e[b]=ne; t[ne]=a; c[ne++]=d;
	}
	int lo=-1,hi=1000001,mid;
	while(lo+1<hi)
	{
		mid=(lo+hi)/2;
		if(ok(mid))hi=mid;
		else lo=mid;
	}
	printf("%d\n",hi==1000001?-1:hi);
	return 0;
}