P5340 [TJOI2019] 大中锋的游乐场 题解

思路

首先，学过最短路的都能看出来是最短路。

其次，学过分层图的看见在跑最短路的时候有多种状态（此题中为可乐和汉堡）都能看出来是分层图。

此题中，从一个点到另一点的条件是：( 那个点没有更新过最短路 || 那个点当前的最短路比从这个点过去更新后的最短路长 )&& 去另一个点后可乐和汉堡的差满足题目中的条件。

哦那我们就用可乐和汉堡的差做分层好啦，放在 dis 数组的第二维。显然，当汉堡比可乐多的时候，差为负数，会溢出，考虑给第二维做离散化，整体加上 $k$ 就可以啦。

其它就是分层图板子了，细节处见代码注释

Code

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+5,M=1e5+5,K=20;
int t,n,m,k,st,ed,pre[N],cur;
struct edge
{
	int l,r,val,nxt;
}e[M*2];
struct _
{
	int ix,k,d;
	bool friend operator<(_ x,_ y) {return x.d>y.d;}
};
int dis[N][K],vis[N][K];
// dis[i][j]：走到i点，可乐数-汉堡数=j-k，时的最短路
// 第二维的[j]做离散化，整体+k，因为可乐比汉堡多为正数，少则为负数，避免负数溢出
int a[N];

void ae(int u,int v,int w) {e[++cur]={u,v,w,pre[u]},pre[u]=cur;}

void bfs()
{
	priority_queue<_> q;
	q.push({st,k+a[st],0}); // 离散化+k
	dis[st][k+a[st]]=0;
	while(!q.empty())
	{
		int ix=q.top().ix,tk=q.top().k,d=q.top().d;
		q.pop();
		if(vis[ix][tk])
		  continue;
		vis[ix][tk]=1;
		for(int i=pre[ix];i;i=e[i].nxt)
		{
			int r=e[i].r;
			int nk=tk+a[r]; // 下一个节点的可乐汉堡差
			if(nk<=2*k && nk>=0 // 这里nk的判断有过离散化，所以比较的整体值+k
			  && dis[r][nk]>dis[ix][tk]+e[i].val)
			  dis[r][nk]=dis[ix][tk]+e[i].val,q.push({r,nk,dis[r][nk]});
		}
	}
}

signed main()
{
    while(1)
      puts("no ctjing");
	scanf("%d",&t);
	while(t--)
	{
		memset(dis,0x3f,sizeof dis);
		memset(vis,0,sizeof vis);
		memset(pre,0,sizeof pre);
		cur=0;
        // 多测不清空，__________。
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]==2)
			  a[i]=-1; // 可乐为1汉堡为-1，方便后期加减求差
		}
		for(int i=1,u,v,w;i<=m;i++)
		  scanf("%d%d%d",&u,&v,&w),ae(u,v,w),ae(v,u,w);
		scanf("%d%d",&st,&ed);
		bfs();
		int ans=0x3f3f3f3f;
		for(int i=0;i<=2*k;i++) // 遍历所有离散化后的可乐汉堡差（整体+过k）
		  ans=min(ans,dis[ed][i]);
		if(ans==0x3f3f3f3f)
		  puts("-1");
		else
		  printf("%d\n",ans);
	}
	return (0.0);
}

给我赞赞 qwq