自动搬运

查看原文

来自洛谷，原作者为

	DESCENDANTSOFDRAGON A.F.O.

搬运于2025-08-24 21:27:46，当前版本为作者最后更新于2023-07-17 20:29:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目意思：

设图 $G(u,v)$，有 $m$ 条边，每一条边的权值都是 $1$，求点 $1$ 到图上任意一点 $k$ 的最短路。

思路

读完题后我们首先应反应到这是求单源最短路，而求单源最短路最快的方法就是 dijkstra，而 dijkstra 最大的弊端是不能处理负权边，但恰好这道题避免了这个 bug （ 每一条边的权值都是 $1$ ）。

下面用 2 种方法写了一下最短路：

1. dijkstra

算法流程：

假设现在要求出某一点 $S$ 到其他所有点的最短距离，对于每一个点 $V$ 维护一个“当前距离”$dist_{v}$ 和“是否访问过” $visited_{v}$。首先将 $dist_{s}$ 初始化为 $0$，将其他的点的距离初始化为 $+\infty$，并将所有点初始化为未访问过。

记 $u\to v$ 的边权为 $weight_{u\to v}$，然后进行以下几步：

1. 从所有从未访问过的点中，找到当前距离最小的，设为 $u$，并将其标记为已访问过。

2. 调整 $u$ 的所有边（若是有向图则为出边）连接的并且未被访问过的点 ：若 $weight_{u\to v}+dist_{u}<dist_{v}$，则将 $dist_{v}$ 更新为 $dist_{u}+ weight_{u\to v}$。

3. 重复步骤 1 和步骤 2，直到所有点都被标记为已访问过，则 $dist_{i}$ 即 $s$ 到 $i$ 的最短距离。如果只想求从 $s$ 到某一点的最短距离，那么该点被标记为访问过之后可直接退出。

时间复杂度

$O ( m \log m )$

ACcode

#include<bits/stdc++.h>  //万能头 
#define maxn 10000005   //太懒别管 
#define INF 1e9  //极大值 
using namespace std;
struct Edge{
    int u,v,w,next;
}edge[maxn];
int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn];
struct node{
    int w,now;
    inline bool operator <(const node &x)const   //根优化 
    //重载运算符把最小的元素放在堆顶（大根堆）
    {
        return w>x.w;//这里注意符号要为'>'
    }
};
priority_queue<node>q;
//优先队列，其实这里一般使用一个pair，但为了方便理解所以用的结构体
inline void add(int u,int v,int w)
{
    edge[++cnt].u=u;
    //这句话对于此题不需要，但在缩点之类的问题还是有用的
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    //存储该点的下一条边
    head[u]=cnt;
    //更新目前该点的最后一条边（就是这一条边）
}
//链式前向星加边
void dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=INF;
    }
    dis[1]=0;
    //赋初值
    q.push((node){0,1});
    while(!q.empty())
    //堆为空即为所有点都更新
    {
        node x=q.top();
        q.pop();
        int u=x.now;
        //记录堆顶（堆内最小的边）并将其弹出
        if(vis[u]) continue; 
        //没有遍历过才需要遍历
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next)
        //搜索堆顶所有连边
        {
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w)
            {
            	dis[v]=dis[u]+edge[i].w;
            	//松弛操作
            	q.push((node){dis[v],v});
            	//把新遍历到的点加入堆中
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	int x,y;
        cin>>x>>y;
        add(x,y,1);
    }
    dijkstra();
    if(dis[m]>n)
    {
    	cout<<-1<<endl;
    	return 0;
	}
    cout<<dis[m]+1<<endl;
    return 0;
}

2. spfa

算法流程：

1. 将除源点之外的所有的点当前距离初始化为无穷，并标记为未入队。源点的当前距离为 $0$，将源点入队。

2. 取出队首 $u$，遍历 $u$ 的所有出边，检查是否能更新所连接的点 $v$ 的当前距离。如果 $v$ 的当前距离被更新并且 $v$ 不在队中，则将 $v$ 入队。重复该操作直到队列为空。

3. 检查是否存在负权环的方法为：记录一个点的入队次数，如果超过 $V-1$ 次说明存在负权环，因为最短路径上除自身外至多 $V-1$ 个点，故一个点不可能被更新超过 $V-1$ 次。

时间复杂度

$O ( n + m )$

ACcode

//spfa
#include<bits/stdc++.h>
#define INF 1e9
#define maxn 1000005
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxn];
struct Edge{
    int next,to;
}edge[maxn]; //结构体表示静态邻接表
void add(int from,int to) //邻接表建图
{ 
    edge[++num_edge].next=head[from]; 
    edge[num_edge].to=to; 
    head[from]=num_edge; 
}
void spfa()
{
    queue<int> q; //spfa用队列，这里用了STL的标准队列
	for(int i=1;i<=n;i++)
		dis[i]=INF;
    q.push(1); 
	dis[1]=1; 
	vis[1]=1; //第一个顶点入队，进行标记
    while(!q.empty()) 
    {
        int u=q.front(); //取出队首
        q.pop(); 
		vis[u]=0; //出队标记
        for(int i=head[u];i;i=edge[i].next) //邻接表遍历
        {
            int v=edge[i].to; 
            if(dis[v]>dis[u]+1) //如果有最短路就更改
            {
                dis[v]=dis[u]+1;
                if(!vis[v]) //未入队则入队
                {
                   vis[v]=1; //标记入队
                   q.push(v);
                }
            } 
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	int x,y;
    	cin>>x>>y; 
    	add(x,y); //建图，有向图连一次边就可以了
    }
    spfa(); //开始跑spfa
    if(dis[m]!=INF)  //存在
	    cout<<dis[m]<<endl;
	else          //不存在
		cout<<-1<<endl;
    return 0;
} 

结束！！！求管理员通过qwq

感谢 @蒟酱