自动搬运

查看原文

来自洛谷，原作者为

	BlachSnake Go hard or go home.

搬运于2025-08-24 21:13:48，当前版本为作者最后更新于2021-07-03 20:56:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

2021/8/29 Update：修改了题解中的两处错误，并在“链式前向星”部分加上了部分注释、增加了建边函数

1.题意

给出一张有 $n$ 个节点，$m$ 条有向边的图，求 $1$ 号点到图中每个节点的最短路。

2.单源最短路问题

给定一个源点（此题中为 $1$ 号点），求从这个源点到图中每个点的最短路径。

接下来先考虑怎么把这个有向图存下来。

用二维数组（设 $a_{i,j}$ 为点 $i$ 到点 $j$ 的距离，空间复杂度 $O(n^2)$）存图？肯定不行，题目规定 $n\le3\times10^5$，妥妥的 MLE。

所以就有了这个东西——

3.链式前向星

链式前向星，是一种利用单向链表存图的数据结构。

那么它长什么样呢？

其实它就是 $n$ 个单向链表，第 $i$ 个单向链表存储从点 $i$ 开始的每条边所指向的点（图中的 to）以及这条边的边权（图中的 weight）。

然后把每个链表的头部用一个 head 数组存起来,如果要遍历某个点开始的所有边，直接写

for(int i=head[x];i;i=next[i])//遍历每一条边

就行了。

那么如何加边呢？

很简单，只需要在链表的头部插入，就像这样：

next[++t]=head[x];//记录后继
to[t]=y;//记录这条边指向的地方
weight[t]=z;//记录边权
head[x]=t;//更新链表头部

存图的问题是解决了，但怎么求最短路呢？

如果用 Dfs 暴搜的话，时间复杂度为 $O(n!)$，稳稳的 TLE。

用 Floyd（其实就是 DP）来做的话，时间复杂度为 $O(n^3)$，也会 TLE。

于是，就有了这么一个算法：

4.Dijkstra 求最短路

Dijkstra 单源最短路算法，是一种用贪心实现的最短路算法，只能在边权值均为正的情况下运行。至于为什么只能在边权值为正的情况下运行，等一下会提到。

这里我们用一个 $\textit{dis}$ 数组存储从源点（这里为点 $1$）到图中每一个点的最短路径长度。

先来看一下算法流程：

初始化，把 $\textit{dis}_1$（源点到源点本身）设为 $0$，$\textit{dis}$ 的 其余值设为 $\infty$；

找到 $\textit{dis}$ 数组的最小值所在的下标 $1$，将其打上标记，并用点 $1$ 的 $\textit{dis}$ 值去更新它周围的点的 $\textit{dis}$ 值，使得 $\textit{dis}_2$ 更新为 $3$，$\textit{dis}_3$ 更新为 $2$，$\textit{dis}_5$ 更新为 $6$；

这里我把 $\textit{dis}_1$ 的数值以及点 $1$ 标蓝了，是因为这个点的最短路已经被求出来了，所以以后不再更新这个点的 $\textit{dis}$ 值。

至于为什么不再更新这个点的 $\textit{dis}$ 值，等一下讲负边权的时候会讲。（这句话你不已经说过一遍了吗……）

点 $2$、点 $3$ 和点 $5$ 因为被点 $1$ 成功更新了 $\textit{dis}$ 值，所以我把它们的 $\textit{dis}$ 值标黄了。

点 $4$ 和点 $6$ 由于没有被遍历到，所以我把它们的 $\textit{dis}$ 值标黑了。

找到 $\textit{dis}$ 数组没打过标记的最小值所在的的下标 $3$，将其打上标记，并用点 $3$ 的 $\textit{dis}$ 值去更新它周围没打过标记的点的 $\textit{dis}$ 值，使得 $\textit{dis}_5$ 更新为 $3$，$\textit{dis}_6$ 更新为 $7$。

点 $1$ 因为已经被打上标记了，所以不用更新它的 $\textit{dis}$ 值。

点 $2$ 因为没被点 $3$ 更新到 $\textit{dis}$ 值，所以我这里把他标红了。

找到 $\textit{dis}$ 数组没打过标记的最小值所在的的下标 $2$，将其打上标记，并用点 $2$ 的 $\textit{dis}$ 值去更新它周围没打过标记的点的 $\textit{dis}$ 值，使得 $\textit{dis}_4$ 更新为 $10$。

找到 $\textit{dis}$ 数组没打过标记的最小值所在的的下标 $5$，将其打上标记，并用点 $5$ 的 $\textit{dis}$ 值去更新它周围的没打过标记点的 $\textit{dis}$ 值，然而并没有更新到任何点的 $\textit{dis}$ 值。

找到 $\textit{dis}$ 数组没打过标记的最小值所在的的下标 $6$，将其打上标记，并用点 $6$ 的 $\textit{dis}$ 值去更新它周围的没打过标记点的 $\textit{dis}$ 值，但仍然没有更新到任何点的 $\textit{dis}$ 值。

另外点 $2$ 到点 $6$ 之间那条边的权值是 $8$，我画图的时候漏了……

找到 $\textit{dis}$ 数组没打过标记的最小值所在的的下标 $4$，将其打上标记，并用点 $4$ 的 $\textit{dis}$ 值去更新它周围的没打过标记点的 $\textit{dis}$ 值，结果还是没有更新到任何点的 $\textit{dis}$ 值。

所有的点都已经被打上了标记，算法结束。

为什么这个算法是正确的呢？

因为你把一个点打上标记后，如果这条路不是最短路，那就必须得从其他的地方绕过来，而这样求出来的路的长度一定比用 Dijkstra 求出来的路要长。

除非这条路上有负边权，不然你怎样也不可能让这条路变成最短路。

这就是为什么 Dijkstra 不能跑负权图的原因。（滑稽）

但是题目规定 $1\le w\le10^7$，没有负边权啊！（哈哈哈）

好的，然后我们就可以开开心心地 AC 了这道题……

了吗？

当然不。

由于 Dijkstra 算法查找 $\textit{dis}$ 值的最小值的下标的时间复杂度为 $O(n)$，而查找下标时一共要查找 $O(n)$ 次，更新每个节点的 $\textit{dis}$ 值时一共又要 $O(m)$ 次，所以总的时间复杂度为 $O(n^2+m)$，还是过不了……

那么，怎么优化这个算法呢？

5.Dijkstra算法的优化

注意每次查找最小值的时候时间复杂度都是 $O(n)$ 的，算法的瓶颈就在这里。

那么我们每次就把这些被更新的点扔进某一个神奇数据结构里，之后只要对着这个神奇数据结构问一发：此时 $\textit{dis}$ 数组里没被打上标记的最小值的下标是多少，再把这个点拉出来，把更新后的点扔进去就行了~

那么问题来了这个神奇数据结构叫什么呢？

二叉堆啊！

当把符合要求的那个点弹出堆后，就把其他更新后的点扔进堆中；

由于扔进去的点的 $\textit{dis}$ 值一定比原先在堆里的这个点的 $\textit{dis}$ 值要小（就是长江后浪推前浪），所以原先在堆里的那些点可以不用管它，因此如果这个点已经被弹出过（就是被标记过）就直接跳过。/xyx

时间复杂度为 $O(m\log m)$，可以通过此题。

至于堆的写法可以参考一下P3378的题解。

6.Code

终于可以上代码了……

不过我这里自己手写了一个堆和一个 pair，实际上也可以用 STL 的 priority_queue，但我不想用……

#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
using namespace std;
const int N=300003,M=5555555;
template<class T>inline void swap(T &x,T &y){T z=x;x=y,y=z;}//交换函数
namespace io{
	inline int Read(){//快速读入数字
		int x=0;
		bool d=0;
		char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')d=1;
		for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
		if(d)x=~x+1;
		return x;
	}
	inline void Print(ll x){//快速输出数字
		if(x){
			if(x<0)x=~x+1,putchar('-');
			short a[22],l;
			for(l=0;x;x/=10)a[++l]=x%10;
			for(;l;--l)putchar(a[l]+48);
		}
		else putchar('0');
		putchar(' ');
	}
}
namespace Classes{
	int nxt[N],to[N],w[N],h[N],t;//链式前向星
	inline void AE(int x,int y,int z){//加边操作
		nxt[++t]=h[x];
		to[t]=y;
		w[t]=z;
		h[x]=t;
	}
	template<class T1,class T2>
	class Pair{//自己手写的pair，也可以用STL的pair
	public:
		T1 x;
		T2 y;
		inline bool operator<(const Pair<T1,T2>b)const{return x==b.x?y<b.y:x<b.x;}//排序函数
	};
	template<class T1,class T2>
	inline Pair<T1,T2> Make_Pair(T1 x,T2 y){//把两个元素做成一个pair
		Pair<T1,T2>a;
		a.x=x,a.y=y;
		return a;
	}
	template<class T>
	class Priority_Queue{//手写堆，也可以用STL的priority_ueue
	private:
		T q[N];
		int l;
		inline void Up(int x){
			int y=x>>1;
			while(y&&q[x]<q[y]){
				swap(q[x],q[y]);
				x=y,y=x>>1;
			}
		}
		inline void Down(int x){
			int y=x<<1;
			while(y<=l){
				if(y<l&&q[y+1]<q[y])++y;
				if(q[y]<q[x])swap(q[x],q[y]),x=y,y=x<<1;
				else break;
			}
		}
	public:
		Priority_Queue(){l=0;}
		inline bool Empty(){return l==0;}
		inline void Clear(){l=0;}
		inline void Push(T x){q[++l]=x,Up(l);}
		inline void Pop(){q[1]=q[l--],Down(1);}
		inline T Top(){return q[1];}
	};
}
using namespace io;
using namespace Classes;
ll d[N];//dis数组，注意一定要开long long
bool b[N];//打标记的数组
Priority_Queue<Pair<ll,int> >q;
inline void Dijkstra(){
	memset(d,63,sizeof(d));//初始化
	d[1]=0;//让源点1的dis值为0
	int x,y,z;
	q.Push(Make_Pair(0ll,1));//把源点插入堆中（假装你已经更新过了源点的dis值）
	while(!q.Empty()){
		x=q.Top().y,q.Pop();
		if(b[x])continue;//如果这个点已经被弹出过就跳过
		b[x]=1;//否则就给它打上标记
		for(int i=h[x];i;i=nxt[i]){
			y=to[i],z=w[i];
			if(d[y]>d[x]+z){//如果这个点的dis值不是最优的
				d[y]=d[x]+z;//更新这个点的dis值
				q.Push(Make_Pair(d[y],y));//把更新后的点插入堆中
			}
		}
	}
}
int main(){
	int n=Read(),m=Read(),x,y,z;
	for(int i=1;i<=m;i++)x=Read(),y=Read(),z=Read(),AE(x,y,z);
	Dijkstra();
	for(int i=1;i<=n;i++)Print(d[i]>=0x3f3f3f3f3f3f3f3fll?-1:d[i]);//三元运算符，如果某个点的dis值没被更新过（就是dis值还是初始化的那个值），直接输出-1
	//否则输出这个点的dis值
	return 0;
}

7.一些闲话

可能会有人就会问了：STL 这么好用，为什么不用 STL 呢？

因为 STL 的堆使用的数组是动态开空间的 vector，而动态开空间又很慢，因此最好能不用 STL 就不用 STL。

另外还有一个叫 SPFA 的最短路算法，时间复杂度为 $O(km)$，其中 $k$ 为常数，平均值为 $2$，在随机数据下极快。

那我们为什么不能用 SPFA 做这道题呢？

因为 SPFA 在某些特殊构造的数据下，时间复杂度会从 $O(km)$ 退化成 $O(nm)$，而此题的 $n$ 和 $m$ 的最大值都为 $3\times10^5$，因此会超时。

所以 NOI2018 就出了这样一个梗：/doge