【P9370】cyber apio

· · 题解

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

分层图好题。

思路

先考虑 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;
}