题解 P3821 【Isaac】

· · 题解

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

言归正传，设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]);
}

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