BZOJ 2763 [JLOI2011]飞行路线

题目大意

给你一个无向图，你有K次机会每次使一条路的长度变为0，问使用不超过K次机会的从1到N的最短路。

分层图最短路裸题。

注意标号是0~N-1的……我当成1~N的之后就崩了

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

#define N 10010
#define M 100010

int n,m,k,S,T,u[M],v[M],w[M],dis[11][N],ans=0x3f3f3f3f;
int to[M],nex[M],val[M],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][S]=0;
	for(int i=0;i<=k;++i)
	{
		memset(use,false,sizeof use);
		for(int j=0;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]]);
				dis[i+1][u[j]]=min(dis[i+1][u[j]],dis[i][v[j]]);
			}
	}
}

int main()
{
	n=RI(),m=RI(),k=RI(),S=RI(),T=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][T]);
	printf("%d\n",ans);
}