P4568 [JLOI2011]飞行路线 最短路+分层图

题意：

给定一张无向图，起点和终点，可以选择其中(k)条边将其边权改为0,求从起点到终点的最小代价

数据范围&性质：(1le nle 10^4,qle mle 5 imes 10^4,1le kle 10)

分析：

没什么好说的，就是分层图裸题，只是我一直不知道有这么一种做法

简单说就是建(k+1)张图，每个点除了和自身这张图的对应点，还和下一张图的对应点连一条边权为0的边，然后有第一张图的起点，向第(k+1)张图的终点跑一遍最短路

代码：

#include<bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
using namespace std;

namespace zzc
{
	const int maxm = 5e4+5;
	const int maxn = 2e4+5;
	int head[maxn*10];
	long long dis[maxn*10];
	bool vis[maxn*10];
	int n,cnt=0,m,k,st,ed;
	
	struct edge
	{
		int to,nxt,val;
	}e[3000005];
	
	void add(int u,int v,int w)
	{
		e[++cnt].to=v;
		e[cnt].val=w;
		e[cnt].nxt=head[u];
		head[u]=cnt;
	}
	
	void dijkstra()
	{
		memset(dis,0x3f,sizeof(dis));
		dis[st]=0;
		priority_queue<pair<long long,int> > q;
		q.push(mk(0,st));
		while(!q.empty())
		{
			int u=q.top().second;
			q.pop();
			if(!vis[u])
			{
				vis[u]=true;
				for(int i=head[u];i;i=e[i].nxt)
				{
					int v=e[i].to;
					if(dis[v]>dis[u]+e[i].val)
					{
						dis[v]=dis[u]+e[i].val;
						q.push(mk(-dis[v],v));
					}
				}
			}
		}
	}
	
	void work()
	{
		int a,b,c;
		scanf("%d%d%d%d%d",&n,&m,&k,&st,&ed);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
			for(int j=1;j<=k;j++)
			{
				add(a+(j-1)*n,b+j*n,0);
				add(b+(j-1)*n,a+j*n,0);
				add(a+j*n,b+j*n,c);
				add(b+j*n,a+j*n,c);
			}
		}
		for(int i=1;i<=k;i++)
		{
			add(ed+(i-1)*n,ed+i*n,0);
		}
		dijkstra();
		printf("%lld
",dis[ed+k*n]);
	}

}

int main()
{
	zzc::work();
	return 0;
}