自动搬运

查看原文

来自洛谷，原作者为

	novax Tomori

搬运于2025-08-24 22:47:45，当前版本为作者最后更新于2023-05-27 23:44:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢土耳其老哥送我铁牌。

分层图好题。

思路

先考虑 $K\leq 30$ 的部分分。

既然求最短距离，那当然是考虑最短路了。

题目要求了到达 $H$ 点就不能再离开，因此需要先建出图跑一个搜索找出所有可以不经由 $H$ 点到达的所有点。若 $H$ 点不能被到达，那么无解。任何可以由起点不经 $H$ 到达的类型 $0$ 城市可以被作为最短路的起点：因为可以先走到这个点上把累积时间清零，再走向 $H$ 点。

很自然地想到把使用除二能力的次数放到状态里：设 $dis_{i,j}$ 表示到达 $i$ 使用了 $j$ 次除二能力的最小距离。

建立分层图，共有 $K+1$ 层：第 $i$ 层对应的 $x$ 点表示使用了 $i$ 次除二能力到达的状态。对于每一条边 $(x_i,y_i,c_i)$，我们在每一层内双向连边。在第 $j$ 层与第 $j+1$ 层之间，我们对于所有 $(x_i,y_i,c_i),arr_{y_i}=2$ 的边，从第 $j$ 层的 $x_i$ 向第 $j+1$ 层的 $y_i$ 连一条权值为 $c_i$ 的边。$H$ 点不连任何出边。

当跨过两层时累积的时间会被除以 $2$，因此需要对层间的边加一个除二标记，表示走过这条边将时间除二。

将前述的可以做起点的点入堆跑 Dijkstra 最短路。为保证转移顺序，需要先以层号为第一关键字，再以距离为第二关键字作为堆的比较方式。

最终在全部 $K+1$ 层的 $H$ 点中取距离最小的就是答案。

对于 $K>30$ 的部分，只需要将 $K$ 与 $70$ 取 $\min$ 即可。

证明：题目只需要你的答案与标准答案误差小于 $10^{-6}$，本题的最大累计时间为 $10^{14}$ 级别，因此当走过层数使得理论最大累计时间都小于 $10^{-6}$ 时，继续走下去就没有意义了。$2^{67}\approx 1.48\times 10^{20}$，因此只要将层数与一个不小于 $67$ 的数取 $\min$ 即可。

代码

#include <algorithm>
#include <queue>
const int Nx=100010;
const double inf=1e24;
int n,m,k,h,ab[Nx];
struct edge{int to,nex,val,typ;};
edge a[300*Nx];
int head[75*Nx],cnt;
void add(int u,int v,int w,int t)
{
	a[++cnt]=edge{v,head[u],w,t};
	head[u]=cnt;
}
struct node
{
	int idx;double val;
	bool operator < (const node &x) const
	{
		if(idx/n!=x.idx/n)
			return idx/n>x.idx/n;
		return val>x.val;
	}
};
int id(int x,int lev){return x+lev*n;}
void find_zpair(int p)
{
	ab[p]=1;
	int i;
	for(i=head[p];i;i=a[i].nex)
	{
		if(ab[a[i].to]==0&&p!=h)
			find_zpair(a[i].to);
	}
}
double dis[75*Nx];
int fin[75*Nx];
void clear_all()
{
	int i;
	for(i=0;i<n;i++)
		ab[i]=0;
	for(i=0;i<=(k+1)*n+1;i++)
		head[i]=dis[i]=fin[i]=0;
	cnt=n=m=k=h=0;
}
double solve(int N,int M,int K,int H,std::vector<int> X,std::vector<int> Y,std::vector<int> C,std::vector<int> arr)
{
	clear_all();
	K=std::min(K,72);
	n=N,m=M,k=K,h=H;
	int i,j,now,fx,fy;
	for(i=0;i<M;i++)
	{
		add(X[i],Y[i],C[i],1);
		add(Y[i],X[i],C[i],1);
	}
	find_zpair(0);
	if(ab[H]==0)
		return -1;
	for(i=0;i<=N;i++)
		head[i]=0;
	cnt=0;
	for(i=0;i<M;i++)
	{
		for(j=0;j<=K;j++)
		{
			if(X[i]!=H)
				add(id(X[i],j),id(Y[i],j),C[i],1);
			if(Y[i]!=H)
				add(id(Y[i],j),id(X[i],j),C[i],1);
			if(j!=K&&X[i]!=H&&arr[Y[i]]==2)
				add(id(X[i],j),id(Y[i],j+1),C[i],2);
			if(j!=K&&Y[i]!=H&&arr[X[i]]==2)
				add(id(Y[i],j),id(X[i],j+1),C[i],2);
		}
	}
	for(i=0;i<=(K+1)*N+1;i++)
		dis[i]=inf,fin[i]=0;
	std::priority_queue<node> hea;
	for(i=0;i<N;i++)
	{
		if(arr[i]==0&&ab[i]==1)
		{
			hea.push(node{i,0});
			dis[i]=0;
		}
	}
	hea.push(node{0,0});
	dis[0]=0;
	while(hea.size())
	{
		node ax=hea.top();
		hea.pop();
		now=ax.idx;
		if(fin[now])
			continue;
		fin[now]=1;
		for(i=head[now];i;i=a[i].nex)
		{
			if(dis[a[i].to]>(dis[now]+a[i].val)/a[i].typ)
			{
				dis[a[i].to]=(dis[now]+a[i].val)/a[i].typ;
				if(!fin[a[i].to])
					hea.push(node{a[i].to,dis[a[i].to]});
			}
		}
	}
	double ans=inf;
	for(i=0;i<=K;i++)
		ans=std::min(ans,dis[id(H,i)]);
	return ans;
}