洛谷P2169正则表达式 题解

题目链接

缩点+最短路

对于同一个强连通分量的点,距离为0。

先Tarjan缩点以后找到强连通分量关系,然后跑Dijkstra最短路。

做最短路的过程中,判断两个点是否在同一个强连通分量里面,如果在,则令边权为0即可。

其实挺水的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>

using LL=long long;

const int inf=0x7fffffff;
const int maxn=2e5+10;

typedef struct EdgeNode
{
int to,val;
EdgeNode *next;
EdgeNode(int to,int val,EdgeNode *nxt):to(to),val(val),next(nxt){}
}*Edge;

struct Point
{
int low,dfn;
bool flag;
int belong;
Edge head;
Point()
{
this->low=this->dfn=0;
this->head=nullptr;
this->flag=0;
}

inline void add(int to,int val)
{
this->head=new EdgeNode(to,val,this->head);
}
}pot[maxn];

int n,m,Time,cnt;

std::stack<int> S;

void Tarjan(int pos)
{
pot[pos].low=pot[pos].dfn=++Time;
S.push(pos);
pot[pos].flag=true;
for(Edge node=pot[pos].head;node!=nullptr;node=node->next)
{
int to=node->to;
if(!pot[to].dfn)
{
Tarjan(to);
pot[pos].low=std::min(pot[pos].low,pot[to].low);
}
else if(pot[to].flag)
pot[pos].low=std::min(pot[pos].low,pot[to].dfn);
}
if(pot[pos].low==pot[pos].dfn)
{
int now;
cnt++;
do
{
now=S.top();
S.pop();
pot[now].flag=false;
pot[now].belong=cnt;
}
while(now!=pos);
}
}

struct POT
{
int pot,dis;
bool operator <(const POT &other) const
{
return this->dis > other.dis;
}
};

std::priority_queue<POT> que;
int dis[maxn];

void Dijkstra(int s)
{
memset(dis,0x7f,sizeof dis);
que.push((POT){s,0});
dis[s]=0;
while(!que.empty())
{
POT P=que.top();
que.pop();
int from=P.pot;
if(dis[from]==P.dis)
{
for(Edge node=pot[from].head;node!=nullptr;node=node->next)
{
int to=node->to;
if(pot[from].belong==pot[to].belong)//在同一个强连通分量里面
node->val=0;
if(dis[to]>dis[from]+node->val)
{
dis[to]=dis[from]+node->val;
que.push((POT){to,dis[to]});
}
}
}
}
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
pot[u].add(v,w);
}
Tarjan(1);
Dijkstra(1);
printf("%d\n",dis[n]);
return 0;
}