正则表达式
问题描述
小 Z 童鞋一日意外的看到小 X 写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符
“0”,“1”，“.”和“*”构成，但是他能够匹配出所有在 OJ 上都 AC 的程序的核心代码！小 Z 大为
颇感好奇，于是他决定入侵小 X 的电脑上去获得这个正则表达式的高级程序。
在 Internet 网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连
接，也就是说存在 A 到 B 的连接不一定存在 B 到 A 的连接，并且有些连接传输速度很快，有些则很慢，
所以不同连接传输所花的时间是有大有小的。另外，如果存在 A 到 B 的连接的同时也存在 B 到 A 的连
接的话，那么 A 和 B 实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为 0。
现在小 Z 告诉你整个网络的构成情况，他希望知道从他的电脑（编号为 1），到小 X 的电脑（编号
为 n）所需要的最短传输时间。
输入
第一行两个整数 n, m， 表示有 n 台电脑，m 个连接关系。
接下来 m 行，每行三个整数 u,v,w；表示从电脑 u 到电脑 v 传输信息的时间为 w。
输出
输出仅一行，为最短传输时间。
数据范围
对于 40%的数据，1<=n<=1000, 1<=m<=10000
对于 70%的数据，1<=n<=5000, 1<=m<=100000
对于 100%的数据，1<=n<=200000, 1<=m<=1000000
算法
- 其实这是一道强连通和最短路的板子题，没什么好讲。只要是属于同一个block的点，他们之间的距离就是0
- 但是由于这个数据比较大，所以算强连通的dfs要手打栈（然而我不会…），于是我就手动开了256M的内存（手动开栈，AC无忧）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
void ff(){
freopen("regexp.in","r",stdin);
freopen("regexp.out","w",stdout);
}
const int MAXN=200020;
struct Edge{
int from,to,w;
Edge(int a,int b,int c):from(a),to(b),w(c){}
};
vector <Edge> edge;
vector <int> G[MAXN];
int n,m;
stack <int> S;
int low[MAXN],pre[MAXN];
int sccno[MAXN];
int dfs_lock,scc_cnt;
void dfs(int u){
pre[u]=low[u]=++dfs_lock;
S.push(u);
int siz=G[u].size();
for (int i=0;i<siz;i++){
int v=edge[G[u][i]].to;
if(!pre[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!sccno[v]){
low[u]=min(low[u],pre[v]);
}
}
if(low[u]==pre[u]){
scc_cnt++;
for (;;){
int x=S.top();S.pop();
sccno[x]=scc_cnt;
if(x==u) break;
}
}
}
void find_scc(){
dfs_lock=scc_cnt=0;
memset(sccno,0,sizeof(sccno));
memset(pre,0,sizeof(pre));
for (int i=1;i<=n;i++){
if(!pre[i]){
dfs(i);
}
}
}
queue <int> q;
bool visited[MAXN];
int dist[MAXN];
void spfa(){
memset(visited,false,sizeof(visited));
memset(dist,0x7f,sizeof(dist));
visited[1]=true;
dist[1]=0;
q.push(1);
while (!q.empty()){
int x=q.front();
q.pop();
visited[x]=false;
int siz=G[x].size();
for (int i=0;i<siz;i++){
Edge &e=edge[G[x][i]];
int v=e.to;
if(sccno[x]==sccno[v]) e.w=0;
int w=e.w;
if(dist[x]+w<dist[v]){
dist[v]=dist[x]+e.w;
if(!visited[v]){
q.push(v);
visited[v]=true;
}
}
}
}
}
int main(){
int size = 128 << 20;
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p));
ff();
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
edge.push_back(Edge(x,y,z));
G[x].push_back(edge.size()-1);
}
find_scc();
spfa();
cout<<dist[n];
return 0;
}