题目背景
小(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)
思路：因为题目要求求的是最短运输时间，且如果两个电脑在一个局域网内，话费时间为0，在同一局域网内即在同一强连通分量内，所以考虑先用tarjan求出所有的强连通分量，然后在两个在同一强连通分量内的点建一条权值为0的边，然后跑堆优化dijkstra，这道题就做完了。
代码：
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<queue>
#include<cstring>
#include<stack>
#define maxn 200001
using namespace std;
int n,m,head[maxn],dis[maxn],bel[maxn],dfn[maxn],js,num,cnt,low[maxn];
bool vis[maxn];
inline int qread() {
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
struct Edge {
int v,w,nxt;
}e[2000007];
struct node {
int x,y;
bool operator < (const node &a) const {return y>a.y;}
};
stack<int>q1;
priority_queue<node>q;
inline void ct(int u, int v, int w) {
e[++num].v=v;
e[num].w=w;
e[num].nxt=head[u];
head[u]=num;
}
void tarjan(int u) {
dfn[u]=low[u]=++cnt;
q1.push(u),vis[u]=1;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
int x;js++;
while(x!=u) {
x=q1.top(),q1.pop();
bel[x]=js;vis[x]=0;
}
}
}
inline void dijkstra() {
memset(dis,0x3f,sizeof(dis));
q.push((node){1,0});
dis[1]=0;
while(!q.empty()) {
int u=q.top().x,d=q.top().y;
q.pop();
if(d!=dis[u]) continue;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w) {
dis[v]=dis[u]+e[i].w;
q.push((node){v,dis[v]});
}
}
}
}
int main() {
n=qread(),m=qread();
for(int i=1,u,v,w;i<=m;++i) {
u=qread(),v=qread(),w=qread();
ct(u,v,w);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;++u) {
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(bel[u]==bel[v]) ct(u,v,0),ct(v,u,0);
}
}
dijkstra();
printf("%d
",dis[n]);
return 0;
}