自动搬运

查看原文

来自洛谷，原作者为

	Diamiko 此人已退役，不用留言了，看不见

搬运于2025-08-24 21:34:43，当前版本为作者最后更新于2020-02-24 12:26:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

核心算法：$Tarjan$缩点+最短路

看标签知道的

我尽量说明的通俗易懂

1.为什么要缩点

来看这样一个图 我们能看到$2-3-4$构成了一个环，这个环内每个点都能到的环中任意一个其他的点，这就叫强连通分量（只是一个通俗的讲法，不是很严谨，但懂这个意思就好了）

在一个有向有环图中才会有强连通分量，在实际做题时我们把一个单点也看做强连通分量

由于本题在一个强连通分量（局域网）内的点之间距离为$0$，我们可以想象到$2-3-4$重合在一起的画面，因为它们之间没有距离，所以我们把一个强连通分量当做一个点建图，就构成了一个DAG，即有向无环图，跑最短路

在这里就不详细介绍$Tarjan$算法了，本题解主要讲思路

2.最短路

$Dijkstra$+堆优化就够了，因为$Floyd$会炸，$SPFA$死了，别的我也不知道了

缩点后的精髓所在就是跑最短路的时候不是按点跑，而是按每一个强连通分量（通常用颜色color表示）

3.代码+注释

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f//伪极大值
using namespace std;
typedef pair<int,int> pii;
struct Node
{
	int head,dis;//链式前向星存储
	int dfn,low,color;
   	 //dfn,low是tarjan算法中固有的，想详细了解可以百度，
         //color是指颜色，也就是该点所属哪个强连通分量
	bool vis;//tarjan算法中这个点有没有在栈里的标志
}node[200005];
struct Edge
{
	int next,len,to;//存边，不解释了
}edge[10005];
int n,m,cnt,color_cnt,x[1000005],y[1000005],l[1000005],deep;
//n,m题目中的意思，color_cnt记录一共有几种颜色（强连通分量），
//x,y,l数组存储输入的边起点，终点和长度，
deep记录搜索深度
stack<int>s;//STL大法好
inline void init()
{
	for(int i=1;i<=n;i++)
	{
		node[i].head
		=node[i].dfn
		=node[i].dis
		=node[i].vis
		=node[i].low
		=0;
	}
	cnt=0;
}//清空原图，便于建新图
inline void addEdge(int u,int v,int w)
{
	edge[++cnt]={node[u].head,w,v};
	node[u].head=cnt;
}
void Tarjan(int u)
{
//纯模板
	s.push(u);
	node[u].dfn=node[u].low=++deep;
	node[u].vis=1;
	for(int e=node[u].head;e;e=edge[e].next)
	{
		int v=edge[e].to;
		if(!node[v].dfn)
		{
			Tarjan(v);
			node[u].low=min(node[u].low,node[v].low);
		}
		else
		{
			if(node[v].vis)
			{
				node[u].low=min(node[u].low,node[v].dfn);
			}
		}
	}
	if(node[u].dfn==node[u].low)
	{
		int tmp;
		color_cnt++;//有新的颜色了
		do
		{
			tmp=s.top();
			s.pop();
			node[tmp].color=color_cnt;
            //记录点的颜色
			node[tmp].vis=0;
		}while(tmp!=u);
	}
}
void Dijkstra()
{
	for(int i=1;i<=n;i++)
	{
		node[i].dis=INF;
	}//初始化各点
	int S=node[1].color;//获取1号点的颜色
	node[S].dis=0;
	priority_queue<pii,vector<pii>,greater<pii> >q;
    //为什么是stl的优先队列，因为我不会手写堆。。
	q.push({0,S});
    //以下都是模板
	while(q.size())
	{
		pii tmp=q.top();
		q.pop();
		int d=tmp.first,u=tmp.second;
		if(d!=node[u].dis)continue;
		for(int e=node[u].head;e;e=edge[e].next)
		{
			int v=edge[e].to;
			if(node[v].dis>d+edge[e].len)
			{
				node[v].dis=d+edge[e].len;
				q.push({node[v].dis,v});
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x[i],&y[i],&l[i]);
        //把边存下来，待会建新图还会有用
		addEdge(x[i],y[i],l[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(!node[i].dfn)
		{
			Tarjan(i);
		}
	}
	init();
    //跑完tarjan，清空原图
	for(int i=1;i<=m;i++)
	{//枚举每一条边，如果连接的两个点颜色不同说明不在一个强连通分量里，那么就连一条边，否则不连
		int u=x[i],v=y[i],w=l[i];
		if(node[u].color!=node[v].color)
		{
			addEdge(node[u].color,node[v].color,w);
		}
	}
	Dijkstra();//跑最短路
	cout<<node[node[n].color].dis<<endl;
    //这里的输出尤其注意，因为我们的新图是按颜色存的，所以输出不应该直接输出n的dis，而是n的颜色的dis，（dis即1-n的最短距离）
	return 0;
}

希望本蒟蒻讲的你们能听懂，不懂可以at我留言

这是我第一篇题解，写题解真是太累了，求过审