Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

Luogu P2169 正则表达式 解题报告

P2169 正则表达式
在Internet网络中的每台电脑并不是直接一对一连通的,而是某些电脑之间存在单向的网络连接,也就是说存在A到B的连接不一定存在B到A的连接,并且有些连接传输速度很快,有些则很慢,所以不同连接传输所花的时间是有大有小的。另外,如果存在A到B的连接的同时也存在B到A的连接的话,那么A和B实际上处于同一局域网内,可以通过本地传输,这样花费的传输时间为0。

现在小Z告诉你整个网络的构成情况,他希望知道从他的电脑(编号为1),到小X的电脑(编号为n)所需要的最短传输时间。

对于100%的数据,$1\leq n\leq200000, 1\leq m\leq 1000000$

解题思路:

Tarjan 缩点 + SPFA/DP

首先观察数据范围,显然这么大的 $n,m$ ,直接跑 $O(nm)$ 的 SPFA 会炸掉。

观察题面,发现如果有 x 和 y 构成一个环(处在同一个 SCC 中),那么他们之间的边长度为 0

这启发我们可以用缩点后再来跑 SPFA ,但是这样的复杂度是不够严谨的,最坏情况下仍旧是 $O(nm)$ 的,只是由于这题水所以可以过。

代码:

SPFA 版本

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
#include <cstdio>
#include <cctype>
#include <cmath>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;
inline int read() {
char v = getchar();int x = 0,f = 1;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
return x * f;
}
const int N = 10010;
const int M = 5000010;

int to[M],hd[N],nxt[M],tot,edg[M];
inline void add(int u,int v,int w) {to[++tot] = v;edg[tot] = w;nxt[tot] = hd[u];hd[u] = tot;}

inline int min(int x,int y) {return x<y?x:y;}
inline int max(int x,int y) {return x>y?x:y;}

using std::stack;

int dfn[N],low[N],ins[N],cnt,num,c[N],n,m,p[N],f[N];
stack <int> s;

void tarjan(int x) {
dfn[x] = low[x] = ++cnt;
s.push(x);ins[x] = 1;
for (int i = hd[x];i;i = nxt[i]) {
if (!dfn[to[i]]) {
tarjan(to[i]);
low[x] = min(low[x],low[to[i]]);
}
else if (ins[to[i]]) {
low[x] = min(low[x],dfn[to[i]]);
}
}
if (dfn[x] == low[x]) {
c[x] = ++num;int y;
do {
y = s.top(),s.pop();
ins[y] = 0;c[y] = num;
}while (x != y);
}
}

int vis[N],dis[N];

void SPFA(int s) {
memset(dis,0x3f,sizeof(dis));
queue <int> q;
vis[s] = 1;dis[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.front();q.pop();
vis[x] = 0;
for (int i = hd[x];i;i = nxt[i]) {
int y = to[i],w = edg[i];
if (c[x] == c[y]) w = 0;
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
if (!vis[y]) {
q.push(y);
vis[y] = 1;
}
}
}
}
}

int main() {
n = read(),m = read();
for (int i = 1;i <= m;++i) {
int x = read(),y = read(),w = read();add(x,y,w);
}
for (int i = 1;i <= n;++i) if (!dfn[i]) tarjan(i);
SPFA(1);
printf("%d",dis[n]);
return 0;
}