题解/洛谷-or-Nsoj/单源最短路径4

---

title: 单源最短路径4 date: 2025-08-19 slug: 题解/洛谷-or-Nsoj/单源最短路径4 tags: [题解, 拓扑排序]

谁说这题水了，这题可太好了

第一眼：$dijistra$水题，但是存在负权边，$GG$，改$SPFA$？就算加了$LLL$和$SLF$也还要$T$，还是$GG$

我嘞个豆o((⊙﹏⊙))o.，是不是突然感觉好无助，不知道怎么写了

注意一下这道题的性质：DAG(有向无环图)，我们可以从这个上面来做文章(yc音)

有向无环是个什么意思，说明我们可以对这个图进行拓扑排序啊！

那再想想拓扑排序，易得只有拓扑排序靠前的点被更新了后面的才可能被影响

那么我们根据这个拓扑序来进行松弛操作，不就可以保证无后效性了吗

queue< int > q;//保存节点
for( int i=1;i<=n;i++ )
	if( deg[i] == 0 )//入度为0
		q.push( i );
vector< int > topsort;//保存拓扑序
while( !q.empty() )//求拓扑序
{
	int t=q.front();
	q.pop();
	topsort.push_back( t );
	for( auto &[x,w]:rode[t] )
	{
		deg[x]--;
		if( deg[x] == 0 )
			q.push( x );
	}
}

for( auto u:topsort )//依据拓扑序进行松弛操作
	for( auto &[v,w]:rode[u] )
		if( min_dis[u]+w < min_dis[v] )
			min_dis[v]=min_dis[u]+w;

计算一下时间复杂度，我们只进行了一次拓扑排序和一次全图松弛操作，只遍历了每个点及其对应边，又因为边有向，所以时间复杂度为$O(n+m)$

利用拓扑序快速松弛是我们在$DAG$中寻求最短路的常用操作，它利用拓扑序的性质从而快速且正确的求解答案