小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（w≤500）。
输出文件仅一行为最短传输时间。
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 23时间：1s 空间：256M
对于40%的数据，1<=n<=1000, 1<=m<=10000
对于70%的数据，1<=n<=5000, 1<=m<=100000
对于100%的数据，1<=n<=200000, 1<=m<=1000000
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
int n,m;
int head[2000610],k,k2,head2[1000610],belong[1000610],gc,dfn[1000610],t,low[1000610],dis[1000610],vis2[1000610],ins[1000610];
int read(){
int a=0,b=1;
char ch=getchar();
while((ch<48||ch>57)&&ch!=‘-‘){
ch=getchar();
}
if(ch==‘-‘){
b=-1;
ch=getchar();
}
while(ch<48||ch>57){
ch=getchar();
}
while(ch>47&&ch<58){
a=a*10+ch-48;
ch=getchar();
}
return a*b;
}
struct ENode{
int v,w,next;
}edge[2000610];
struct ENode2{
int v,w,next;
}edge2[2000610];
void add(int u,int v,int w){
k++;
edge[k].v=v;
edge[k].w=w;
edge[k].next=head[u];
head[u]=k;
}
void add2(int u,int v,int w){
k2++;
edge2[k2].v=v;
edge2[k2].w=w;
edge2[k2].next=head2[u];
head2[u]=k2;
}
stack<int> sTar;
stack<int> q2;
void Tarjan(int u){
t++;
dfn[u]=low[u]=t;
ins[u]=1;
sTar.push(u);
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(ins[v]){
low[u]=min(low[u],dfn[v]);
}
}
}
if(low[u]>=dfn[u]){
gc++;
int i;
do{
i=sTar.top();
ins[i]=0;
belong[i]=gc;
sTar.pop();
}while(i!=u);
}
}
void spfa(){
memset(vis2,0,sizeof(vis2));
memset(dis,0x3f3f3f,sizeof(dis));
q2.push(belong[1]);
dis[belong[1]]=0;
vis2[belong[1]]=1;
while(q2.size()){
int h=q2.top();
q2.pop();
vis2[h]=0;
for(int i=head2[h];i;i=edge2[i].next){
int v=edge2[i].v;
if(dis[v]>dis[h]+edge2[i].w){
dis[v]=dis[h]+edge2[i].w;
if(!vis2[v]){
q2.push(v);
vis2[v]=1;
}
}
}
}
}
int main(){
int u,v,w;
n=read(),m=read();
for(int i=0;i<m;i++){
u=read(),v=read(),w=read();
add(u,v,w);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
Tarjan(i);
}
}
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=edge[j].next){
int v=edge[j].v;
if(belong[i]!=belong[v]){
add2(belong[i],belong[v],edge[j].w);
}
}
}
spfa();
printf("%d\n",dis[belong[n]]);
return 0;
}
原文：https://www.cnblogs.com/xiongchongwen/p/11391370.html