洛谷P2169 正则表达式

题目背景

小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：

说明

对于40%的数据，1<=n<=1000, 1<=m<=10000

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

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

  1 /*by SilverN*/
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<queue>
  8 using namespace std;
  9 const int mxn=1e6+20;
 10 int read(){
 11     int x=0,f=1;char ch=getchar();
 12     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 14     return x*f;
 15 }
 16 struct edge{
 17     int v,dis;
 18     int nxt;
 19 }e[mxn],mp[mxn];
 20 int hd1[mxn],hd2[mxn];
 21 int mct1=0,mct2=1;
 22 void add_edge(int u,int v,int dis){
 23     e[++mct1].v=v;e[mct1].nxt=hd1[u];e[mct1].dis=dis;hd1[u]=mct1;
 24     return;
 25 }
 26 void add_edge2(int u,int v,int dis){
 27     mp[++mct2].v=v;mp[mct2].nxt=hd2[u];mp[mct2].dis=dis;hd2[u]=mct2;
 28     return;
 29 }
 30 int n,m;
 31 //
 32 int dtime=0;
 33 int dfn[mxn],low[mxn];
 34 bool inq[mxn];
 35 int st[mxn],top=0;
 36 int belone[mxn],cnt=0;
 37 void tarjan(int u){
 38     dfn[u]=low[u]=++dtime;
 39     inq[u]=1;
 40     int i,j;
 41     st[++top]=u;
 42     for(i=hd1[u];i;i=e[i].nxt){
 43         int v=e[i].v;
 44         if(!dfn[v]){
 45             tarjan(v);
 46             low[u]=min(low[u],low[v]);
 47         }
 48         else if(inq[v]){
 49             low[u]=min(low[u],dfn[v]);
 50         }
 51     }
 52     int v=-1;
 53     if(dfn[u]==low[u]){
 54         cnt++;
 55         do{
 56             v=st[top--];
 57             inq[v]=0;
 58             belone[v]=cnt;
 59         }while(u!=v);
 60     }
 61     return;
 62 }//
 63 
 64 int dis[mxn];
 65 queue<int>q;
 66 void SPFA(){
 67     memset(inq,0,sizeof inq);
 68     memset(dis,0x3f,sizeof dis);
 69     q.push(belone[1]);
 70     dis[belone[1]]=0;
 71     inq[belone[1]]=1;
 72     int i,j;
 73     while(!q.empty()){
 74         int u=q.front();q.pop();
 75         for(i=hd2[u];i;i=mp[i].nxt){
 76             int v=mp[i].v;
 77             if(dis[v]>dis[u]+mp[i].dis){
 78                 dis[v]=dis[u]+mp[i].dis;
 79                 if(!inq[v]){
 80                     inq[v]=1;
 81                     q.push(v);
 82                 }
 83             }
 84         }
 85         inq[u]=0;
 86     }
 87     return;
 88 }
 89 void solve(){
 90     int i,j;
 91     for(i=1;i<=n;i++){
 92         for(j=hd1[i];j;j=e[j].nxt){
 93             int v=e[j].v;
 94             if(belone[i]==belone[v])continue;
 95             add_edge2(belone[i],belone[v],e[j].dis);
 96         }
 97     }
 98     SPFA();
 99     printf("%d
",dis[belone[n]]);
100     return;
101 }
102 //
103 int main(){
104     n=read();m=read();
105     int i,j;
106     int u,v,d;
107     for(i=1;i<=m;i++){
108         u=read();v=read();d=read();
109         add_edge(u,v,d);
110     }
111     for(i=1;i<=n;i++)
112         if(!dfn[i])
113             tarjan(i);
114     solve();
115     return 0;
116 }