自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 21:53:05，当前版本为作者最后更新于2019-07-29 15:06:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

话说我刚开始写时还是紫题怎么写到一半就黑了

言归正传，设$f[t][i][j]$为$t$时刻从$i$到$j$的路径中最长边的最小值，$l[i][j]$表示房间$i$到房间$j$的通道长度（之间没有通道就算作无限大）

可以得到递推式$f[t][i][j]=min(max(f[t-1][i][u],l[u][j])|1<=u<=n)$，特别的，$f[1][i][j]=l[i][j]$，$f[k][s][t]$即为答案

因为满足结合律，所以用矩阵来优化

至于怪物的情况可以用和这题类似的方法处理，把12个时刻作为一个轮回，对于每一个时刻建立一个邻接矩阵$bzjx$，若$T(1<=T<=12)$时刻房间$j$有怪物，则$bzjx[T][i][j]=$无限大，并计算前$T$个$bzjx$运算的结果，用$jx[T]$储存

设$k=p*12+q$，计算${(jx[12])}^{p}*jx[q]$($p$为0则$jx[q]即为答案$，$q$为0则直接计算${(jx[12])}^{p}$)

注意不存在路径时输出'IMP0SSBLE!!'（要输出引号且中间O为0）

时间复杂度大概$O(n^{3}logk)$(反正能过管那么多干嘛)

代码就凑合着看吧

#include<bits/stdc++.h>
using namespace std;
const int N=50;
const int M=12;
const long long oo=2e10;
long long bzjx[M+1][N+1][N+1],jx[M+1][N+1][N+1];
long long ans[N+1][N+1],b[N+1][N+1],l[N+1][N+1],ll[N+1][N+1];
int n,m,s,t,k,a;
void POW(int x)//矩阵
{
	if(x==1){memcpy(b,jx[M],sizeof(jx[M]));return;}
	POW(x>>1);
	memcpy(l,b,sizeof(b));
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    b[i][j]=oo;
	if(x&1)
	{
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		    ll[i][j]=oo;
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		    for(int p=1;p<=n;p++)
		      ll[i][j]=min(ll[i][j],max(l[i][p],l[p][j]));
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		    for(int p=1;p<=n;p++)
		      b[i][j]=min(b[i][j],max(ll[i][p],jx[M][p][j]));
	}
	else
	{
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		    for(int p=1;p<=n;p++)
		      b[i][j]=min(b[i][j],max(l[i][p],l[p][j]));
	}
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
	for(int i=1;i<=M;i++)
	  for(int j=1;j<=n;j++)
	    for(int p=1;p<=n;p++)
	      jx[i][j][p]=bzjx[i][j][p]=oo;
	while(m--)//初始化矩阵
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		for(int i=1;i<=M;i++)bzjx[i][u][v]=bzjx[i][v][u]=(long long)w;
	}
	scanf("%d",&a);
	while(a--)//处理有怪物的情况
	{
		int T;
		scanf("%d",&T);
		int ro[4];
		for(int i=0;i<T;i++)scanf("%d",ro+i);
		for(int i=1;i<=M;i++)
		  for(int j=1;j<=n;j++)
		    bzjx[i][j][ro[i%T]]=oo;
	}
	memcpy(jx[1],bzjx[1],sizeof(bzjx[1]));
	for(int i=2;i<=M;i++)
	  for(int j=1;j<=n;j++)
	    for(int p=1;p<=n;p++)
	      for(int l=1;l<=n;l++)
	        jx[i][j][p]=min(jx[i][j][p],max(jx[i-1][j][l],bzjx[i][l][p]));
	if(k/M)
	{
		POW(k/M);
		int r=k%M;
		if(r)
		{
			for(int i=1;i<=n;i++)
			  for(int j=1;j<=n;j++)
			    ans[i][j]=oo;
			for(int i=1;i<=n;i++)
			  for(int j=1;j<=n;j++)
			    for(int p=1;p<=n;p++)
				  ans[i][j]=min(ans[i][j],max(b[i][p],jx[r][p][j]));
		}//有余数，所得结果再和jx[r]进行运算得到答案
		else memcpy(ans,b,sizeof(b));//刚好除尽，将矩阵快速冥后的结果直接复制
	}
	else memcpy(ans,jx[k],sizeof(jx[k]));//不足12，直接复制
	if(ans[s][t]==oo)printf("'IMP0SSBLE!!'");
	else printf("%lld",ans[s][t]);
}

可能讲的不是很清楚请见谅，毕竟蒟蒻语文不好