正则表达式

题目背景
小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。

输出格式
输出文件仅一行为最短传输时间。

输入输出样例
输入 #1复制
3 2
1 2 1
2 3 1
输出 #1复制
2
输入 #2复制
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2
输出 #2复制
3
说明/提示
对于40%的数据，1<=n<=1000, 1<=m<=10000

对于70%的数据，1<=n<=5000, 1<=m<=100000

对于100%的数据，1<=n<=200000, 1<=m<=1000000

比较明显的缩点之后最短路。

所以我们直接缩点，然后对缩点之后的图跑最短路即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,M=1e6+10;
int n,m,low[N],dfn[N],col[N],vis[N],co,cnt,a[M],b[M],c[M],d[N];
int head[N],nex[M],to[M],tot;
stack<int> st;
vector<int> v1[N],v2[N];
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void tarjan(int x){
	dfn[x]=low[x]=++cnt;	st.push(x),vis[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]);	low[x]=min(low[x],low[to[i]]);
		}else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
	}
	if(dfn[x]==low[x]){
		int u; co++;
		do{
			u=st.top();	st.pop();	col[u]=co; vis[u]=0;
		}while(u!=x);
	}
}
int dijkstra(int s,int t){
	priority_queue<pair<int,int> > q;	q.push({0,s});
	int vis[N]={0};	memset(d,0x3f,sizeof d); d[s]=0;
	while(q.size()){
		int u=q.top().second; q.pop();
		if(vis[u])	continue;	vis[u]=1;
		for(int i=0;i<v1[u].size();i++){
			int v=v1[u][i],val=v2[u][i];
			if(d[v]>d[u]+val){
				d[v]=d[u]+val;
				if(!vis[v])	q.push({-d[v],v});
			}
		}
	}
	return d[t];
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)	
		scanf("%d %d %d",&a[i],&b[i],&c[i]),add(a[i],b[i]);
	for(int i=1;i<=n;i++)	if(!dfn[i])	tarjan(i);
	for(int i=1;i<=m;i++){
		if(col[a[i]]==col[b[i]])	continue;
		v1[col[a[i]]].push_back(col[b[i]]);	v2[col[a[i]]].push_back(c[i]);
	}
	cout<<dijkstra(col[1],col[n])<<endl;
	return 0;
}