题解：电网的传送迷宫

· · 题解

暴力做法是直接建出分层图，然后 01bfs，复杂度是 O(nm q) 的，这里就不再赘述。

首先，由于第 i 次传送到的点是不同的，所以可以考虑先设 f_i 表示到 (c_i,d_i) 的最小代价，然后考虑求解这个 f，由于传送门之间本质相同，所以 f_i 就是 f_{i-1} 加上离 (c_{i-1},d_{i-1}) 最近的传送门到它的距离。

那么，我们可以新建节点 s，让 s 向所有的传送门连一条边权为 0 的边，然后其他相邻网格连 1 权的边，以 s 为源点跑单源最短路，得到数组 dis_{1,x,y} 就是从距离 (x,y) 最近的传送门到它的距离，然后套用刚刚的转移方式可以预处理出 f，如果最短路使用迪杰斯特拉算法是 O(nm\log n) 的，但是使用 01bfs 算法可以做到 O(nm)，然后考虑 01bfs 在干什么，其实就是将所有传送门提前入队一次，再跑边权为 1 的最短路，所以可以直接使用 bfs 解决这个问题。

预处理完 f 后，可以直接想到一个暴力做法：新建节点 s，s 向 (a_i,b_i) 连边权为 f_i 的边，向起点连边权为 0 的边，然后跑最短路，这样显然是对的，但是复杂度是 O(nm\log n)，无法通过。沿用刚刚的思路，我们发现只有这些 s 出发的边是特殊的，直接使用迪杰斯特拉不优，我们希望可以将它改造为 bfs。这依然是可行的，我们发现 bfs 和迪杰斯特拉唯一的区别是我们把一个优先队列变成了一个普通队列，这是因为对于边权为 1 的图，在队列直接向后插入元素可以保证队列元素是单调的，我们希望依然在这个图上也可以保持这个性质，事实上也很简单，我们从小到大考虑一个传送门的终点 (c_i,d_i)，我们先假装在跑一个普通的 bfs，对于这个 bfs 的队列，最大值与最小值相差必然不超过 1，设队列队首元素的值为 k，那么如果 f_i\le k+1，此时插入 f_i 进入队列末尾是依然满足的 bfs 的性质的，然后你发现这样也一直满足这是一个优先队列的要求，所以直接维护一个指针 p，在 bfs 每一轮拓展之后，若满足 f_p\le k+1，则拓展指针 p ，将 (c_i,d_i) 加入队列，即可满足要求。这部分的时间复杂度为 O(nm)

所以总复杂度就是 O(nm)，由于这只是 T2，所以没有卡 O(nm\log n) 的做法。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int opt,n,m,p,q;
int id(int x,int y){return (x-1)*m+y;}
char ch[1005*1005];
struct edge{
    int from,to;
}e[1005*1005*10];int head[1005*1005],siz;
void addedge(int x,int y){
    e[++siz].to=y;
    e[siz].from=head[x],head[x]=siz;
}
int b[1005*1005],f[1005*1005],dis1[1005*1005],dis2[1005*1005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>opt>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch[id(i,j)];
            dis1[id(i,j)]=dis2[id(i,j)]=1e15;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ch[id(i,j)]=='#') continue;
            if(i-1>=1&&ch[id(i-1,j)]!='#') addedge(id(i,j),id(i-1,j));
            if(i+1<=n&&ch[id(i+1,j)]!='#') addedge(id(i,j),id(i+1,j));
            if(j-1>=1&&ch[id(i,j-1)]!='#') addedge(id(i,j),id(i,j-1));
            if(j+1<=m&&ch[id(i,j+1)]!='#') addedge(id(i,j),id(i,j+1));
        }
    }
    int sx,sy,fir,tx,ty,ed=0;
    cin>>sx>>sy;fir=id(sx,sy);
    cin>>p>>q;
    if(opt==1) cin>>tx>>ty,ed=id(tx,ty);
    queue<int> Q;
    for(int i=1;i<=p;i++){
        int x,y;cin>>x>>y;
        Q.push(id(x,y));
        dis1[id(x,y)]=0;
    }
    for(int i=1;i<=q;i++){
        f[i]=1e15;
        int x,y;cin>>x>>y;
        b[i]=id(x,y);
    }
    b[0]=fir;
    while(!Q.empty()){
        int now=Q.front();Q.pop();
        for(int i=head[now];i;i=e[i].from){
            int u=e[i].to;
            if(dis1[u]>dis1[now]+1){
                dis1[u]=dis1[now]+1;
                Q.push(u);
            }
        }
    }
    for(int i=1;i<=q;i++){
        if(dis1[b[i-1]]>=1e15) continue;
        f[i]=f[i-1]+dis1[b[i-1]];
    }
    Q.push(b[0]);
    int pos=1;
    dis2[b[0]]=0;
    while(!Q.empty()){
        int now=Q.front();Q.pop();
        for(int i=head[now];i;i=e[i].from){
            int u=e[i].to;
            if(dis2[u]>dis2[now]+1){
                dis2[u]=dis2[now]+1;
                Q.push(u);
            }
        }
        while(pos<=q&&(Q.empty()||f[pos]<=dis2[Q.front()]+1)){
            Q.push(b[pos]);
            dis2[b[pos]]=min(dis2[b[pos]],f[pos]);
            pos++;
        }
    }
    if(opt){
        if(dis2[ed]>=1e15) cout<<-1;
        else cout<<dis2[ed];
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dis2[id(i,j)]>=1e15) cout<<-1<<' ';
            else cout<<dis2[id(i,j)]<<' ';
        }cout<<'\n';
    }
}