BZOJ 2662 [BeiJing wc2012]冻结

题目大意

给你一个无向图，你有K次机会每次使一条路的长度变为原来的$\frac{1}{2}$，问使用不超过K次机会的从1到N的最短路。

这题一看$N \times K$非常非常小，那直接上分层图最短路就好了。

在每一层上跑堆优化Dijkstra()，之后每层中间枚举一下哪条路使用机会就可以了。

注意每一层开始都把所有点都加进去！

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 60
#define M 1010

int n,m,k,u[M],v[M],w[M],dis[N][N],ans=0x3f3f3f3f;
int to[M<<1],nex[M<<1],val[M<<1],head[N],tot;
bool use[N];

priority_queue<pair<int,int> >q;

inline int RI()
{
	int ret=0;char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

inline void AE(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}

void dijkstra()
{
	memset(dis,0x3f,sizeof dis);
	dis[0][1]=0;
	for(int i=0;i<=k;++i)
	{
		memset(use,false,sizeof use);
		for(int j=1;j<=n;++j)
			q.push(pair<int,int>(-dis[i][j],j));
		while(!q.empty())
		{
			int tmp=q.top().second;
			q.pop();
			if(use[tmp]) continue;
			use[tmp]=true;
			for(int j=head[tmp];j;j=nex[j])
				if(dis[i][to[j]]>dis[i][tmp]+val[j])
				{
					dis[i][to[j]]=dis[i][tmp]+val[j];
					q.push(pair<int,int>(-dis[i][to[j]],to[j]));
				}
		}
		if(i!=k)
			for(int j=1;j<=m;++j)
			{
				dis[i+1][v[j]]=min(dis[i+1][v[j]],dis[i][u[j]]+(w[j]>>1));
				dis[i+1][u[j]]=min(dis[i+1][u[j]],dis[i][v[j]]+(w[j]>>1));
			}
	}
}

int main()
{
	n=RI(),m=RI(),k=RI();
	for(int i=1;i<=m;++i)
		u[i]=RI(),v[i]=RI(),w[i]=RI(),AE(u[i],v[i],w[i]),AE(v[i],u[i],w[i]);
	dijkstra();
	for(int i=0;i<=k;++i) ans=min(ans,dis[i][n]);
	printf("%d\n",ans);
	return 0;
}