题解 P2169 【正则表达式】
Diamiko
·
·
题解
核心算法：Tarjan缩点+最短路
看标签知道的
我尽量说明的通俗易懂
1.为什么要缩点
来看这样一个图
我们能看到2-3-4构成了一个环，这个环内每个点都能到的环中任意一个其他的点，这就叫强连通分量（只是一个通俗的讲法，不是很严谨，但懂这个意思就好了）
在一个有向有环图中才会有强连通分量，在实际做题时我们把一个单点也看做强连通分量
由于本题在一个强连通分量（局域网）内的点之间距离为0，我们可以想象到2-3-4重合在一起的画面，因为它们之间没有距离，所以我们把一个强连通分量当做一个点建图，就构成了一个DAG，即有向无环图，跑最短路
在这里就不详细介绍Tarjan算法了，本题解主要讲思路
2.最短路
缩点后的精髓所在就是跑最短路的时候不是按点跑，而是按每一个强连通分量（通常用颜色color表示）
### 3.代码+注释
```cpp
#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我留言
这是我第一篇题解，写题解真是太累了，求过审