自动搬运

查看原文

来自洛谷，原作者为

	WorldBest丶牛顿 **

搬运于2025-08-24 22:02:27，当前版本为作者最后更新于2018-09-12 01:04:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

注意 这篇题解有四份代码，AC代码需要您们拼凑一下qwq

对于原来的电路来说，我们可以将每个顶点和它周围的点相连
点之间存在导线的两个点连一条边权为 $0$ 的边，不存在导线的连一条边权为 $1$ 的边
为什么这么做呢，原来有边的两个点本来就是通路的，也就不需要加边权
原来没有边的两个点，需要将导线转一下，那转动导线的操作也就是经过一条边权为 $1$ 的边，最短路的长度加 $1$

这样就能将这道题转化为一个求从左上角到右下角的最短路的题目
很明显这是一个网格图，而且时限 $150ms$ 最好不要用某个算法

我先是写了一个优先队列优化的 $Dijkstra$（开了 $O2$ 过了，不开 $80-90$ 左右）

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;

const int INF=19260817;
int n,m,cnt,sum;
int left_up,left_down,right_up,right_down;
char f[505];
int head[1100001],d[1100001];

struct edge
{
    int next,w,v;
}e[1100001];

void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

struct node
{
    int u,d;
    bool operator<(const node& rhs) const{
        return d>rhs.d;
    }
}; //用cmp的写法wa了一个晚上之后我就再也不那么写了

void Dijkstra()
{
    sum=(m+1)*(n+1);//这是总的节点数
    priority_queue<node> q;
    for(int i=1;i<=sum;i++) d[i]=INF;
    d[1]=0;
    q.push((node){1,d[1]});
    while(!q.empty())
    {
        node x=q.top(); q.pop();
        int u=x.u;
        if(x.d!=d[u]) continue;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[u]+w<d[v])
            {
                d[v]=d[u]+w;
                q.push((node){v,d[v]});
            }
        }
    }
    if(d[sum]==INF) cout<<"NO SOLUTION";
    else cout<<d[sum];
} 

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
    	cin>>f;
        for(int j=0;j<m;++j)
        {
        	left_up=(m+1)*i+j+1;
    		right_up=(m+1)*i+j+2;
    		left_down=(m+1)*(i+1)+j+1;
    		right_down=(m+1)*(i+1)+j+2;
            //处理节点编号，一条边占一个格子的话就会有四个顶点
            if(f[j]==92)//不知道转义符的我就只能写个ASCII码了
            {
               	add(left_up,right_down,0);
               	add(right_down,left_up,0);//无向图正反存一次
               	add(left_down,right_up,1);
                add(right_up,left_down,1);
           	}
            if(f[j]==47)
            {
            	add(left_down,right_up,0);
                add(right_up,left_down,0);
                add(left_up,right_down,1);
                add(right_down,left_up,1);
            }
        }
    }
    Dijkstra();
    return 0;
}

虽然过了，但是这种方法肯定是不完美的（毕竟开 $O2$ 才行）。
很明显，我这个存图的方式常数太大，那我们可以改一下存图

void add(int u,int v,int w)
{
    e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].v=u;e[cnt].w=w;e[cnt].next=head[v],head[v]=cnt;
}//顺便也改一下，写起来更加方便了

//main函数中的存图
	for(int i=1;i<=n+1;++i)
        for(int j=1;j<=m+1;++j)
            mark[i][j]=++tot;//预处理出每个顶点的编号
    for(int i=1;i<=n;++i)
    {
    	cin>>f;
        for(int j=1;j<=m;++j)
        {
            if(f[j-1]=='/')
            {
            	add(mark[i][j],mark[i+1][j+1],1);//调整一下存图函数就方便了很多
               	add(mark[i+1][j],mark[i][j+1],0);
            }
            else
            {
               	add(mark[i][j],mark[i+1][j+1],0);
               	add(mark[i+1][j],mark[i][j+1],1);
           	}
        }
    }

但是这种写法还是只有 $90$ 分左右，那该怎么办呢？
注意到 $Dijkstra$ 的堆优化中会重复加点很多次
在 $Dijkstra$ 中，我们明明只是需要找出 $dis$ 值最小的点不是吗

那我们就可以使用线段树来优化查询操作（只需要单点修改呢）
只要最初将值都设为 $INF$ ，起点设为 $0$ ，线段树储存最小值，
将走过的点也设为 $INF$ ， $Dijkstra$ 的时候判断树根的值是否等于 $INF$ ，
如果等于的话就没有点能更新了，就做完了
可以看一下告诉我这个方法的 @yizimi远欣 大佬的博客

struct segment_tree
{
	int minx[1100001],tag[1100001];
	void push_up(int p)
	{
		minx[p]=min(minx[p<<1],minx[p<<1|1]);
		tag[p]=(minx[p<<1]<minx[p<<1|1])?tag[p<<1]:tag[p<<1|1];
        //minx存最小值，tag存拥有这个值的点的编号
	}
	void build(int l,int r,int p)
	{
		if(l==r)
		{
			minx[p]=d[l];
			tag[p]=l;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,p<<1);
		build(mid+1,r,p<<1|1);
		push_up(p);
	}
	void update(int now,int l,int r,int p,int k)
	{
		if(l==r)
		{
			minx[p]=k;
			return;
		}
		int mid=(l+r)>>1;
		if(now<=mid) update(now,l,mid,p<<1,k);
		else update(now,mid+1,r,p<<1|1,k);
		push_up(p);
	}
}tree;

void Dijkstra()
{
    for(int i=2;i<=tot;i++) d[i]=INF;
    tree.build(1,tot,1);
    while(tree.minx[1]<INF)//如果线段树的树根的值为INF，那所有能找的点都找完了
    {
        int u=tree.tag[1];
        tree.update(u,1,tot,1,INF);//走过的点设为INF，相当于vis数组
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                tree.update(v,1,tot,1,d[v]);//树上更新
            }
        }
    }
    if(d[tot]==INF) cout<<"NO SOLUTION";
    else cout<<d[tot];
} 

为什么还是过不了啊，递归线段树的常数这么大吗 $qwq$
等一下，我们只需要单点修改，查询都不用
那我们为什么不写一棵常数很小，代码又短的zkw线段树呢

struct segment_tree
{
	int bit;
	int minx[1100001],tag[1100001];//真的是习惯了写sum，当成最小值看就行了
	void push_up(int n)
	{
		minx[n]=min(minx[n<<1],minx[n<<1|1]);
		tag[n]=minx[n<<1]<minx[n<<1|1]?tag[n<<1]:tag[n<<1|1];
	}
	void build(int n)
	{
		for(bit=1;bit<=n+1;bit<<=1);
		for(int i=bit+1;i<=(bit<<1)-1;++i)
		{
        	 //注意这里结束循环的条件为(bit<<1)-1，这是因为zkw线段树需要把叶子填满，
             //如果不填满的话最后就会有编号大于n的点值为0，树根始终为0，陷入死循环
			 minx[i]=i-bit==1?0:INF;//将出发点的dis值设为0
			 tag[i]=i-bit;
		}
		for(int i=bit-1;i>=1;--i)
			push_up(i);
	}
	void update(int n,int k)
	{
		for(minx[n+=bit]=k,n>>=1;n;n>>=1)
			push_up(n);
	}
}tree;

至此，就可以满分通关啦！