正则表达式

Description

小沐同学一日意外的看到小原写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符“0”,“1”，“.”和“*”构成，但是他能够匹配出所有在OJ 上都AC 的程序的核心代码！小沐颇感好奇，于是他决定入侵小原的电脑上去获得这个正则表达式的高级程序。

在互联网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在 A 到 B 的连接不一定存在B 到A 的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。

另外，如果存在A 到B 的连接的同时也存在B 到A 的连接的话，那么A 和B 实际上处于同一局域网内，可以通过本地传输，所以花费的传输时间为0。现在小沐告诉你整个网络的构成情况，他希望知道从他的电脑（编号为 1）到小原的电脑（编号为 n）所需要的最短传输时间。

Input

第一行两个整数 n,m，表示有n 台电脑，m 个连接关系。
接下来 m 行，每行三个整数 u,v,w；表示从电脑 u 到电脑v 传输信息的时间为w。

Output

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

Sample Input

输入样例1：
3 2
1 2 1
2 3 1
输入样例2：
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2

Sample Output

输出样例1：
2
输出样例2：
3

Hint

【数据范围】
对于 40%的数据，1<=n<=1000,1<=m<=10000
对于 70%的数据，1<=n<=5000,1<=m<=100000
对于 100%的数据，1<=n<=200000,1<=m<=1000000,1<=w<=10000

【分析】

看完题应该就知道怎么做了。

step1：使用Kosaraju算法，求出强联通分量SCC。

step2：重新构图，把scc看作结点，然后连边后用SPFA，或Dijkstra+堆做一次最短路，求出1所在的scc到N所在的scc最短路即可。

（注：此题n较大，要用手工栈）；

【代码】

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
queue<int>Q;        //Q为SPFA的队列 
stack<int>S;        //S为Kosaraju的手工栈 
const int maxn=200005;
const int maxm=1000005;
const int INF=999999999;
int N,M,tot,scc,pos;
int xt[maxm],yt[maxm],zt[maxm],nextt[maxm],lastt[maxn];    //正向图 
int x2[maxm],y2[maxm],z2[maxm],next2[maxm],last2[maxn];    //反向图 
int x[maxm],y[maxm],z[maxm],next[maxm],last[maxn];    //scc作为结点的图 
int loc[maxn],list[maxn],dis[maxn];
bool vis[maxn];
void _in(int &x)
{
     char t=getchar();
     while(t<'0'||'9'<t) t=getchar();
     for(x=t-'0',t=getchar();'0'<=t&&t<='9';x=x*10+t-'0',t=getchar());
}
void _init()
{
     _in(N);_in(M);
     for(int i=1;i<=M;i++)
     {
         _in(xt[i]);_in(yt[i]);_in(zt[i]);
         nextt[i]=lastt[xt[i]];
         lastt[xt[i]]=i;
         x2[i]=yt[i];y2[i]=xt[i];z2[i]=zt[i];
         next2[i]=last2[x2[i]];
         last2[x2[i]]=i;
     }
}
void _DFS1(int x)        //Kosaraju算法 
{
	while(!S.empty()) S.pop();      
	S.push(x);
	while(!S.empty())
	{
		x=S.top();
		vis[x]=true;
		for(int i=lastt[x];i;i=nextt[i])
		    if(!vis[yt[i]])
		    {
		    	S.push(yt[i]);
		    	goto END;
		    }
		list[++pos]=x;
		S.pop();
		END:continue;
	}
}
void _DFS2(int x)
{
	while(!S.empty()) S.pop();
	S.push(x);
	while(!S.empty())
	{
		x=S.top();
		loc[x]=scc;
		vis[x]=true;
		for(int i=last2[x];i;i=next2[i])
		    if(!vis[y2[i]])
		    {
		    	S.push(y2[i]);
		    	goto END;
		    }
		S.pop();
		END:continue;
	}
}
void _SPFA(int Start)
{
     memset(vis,sizeof(vis));
     int t;
     dis[Start]=0;
     Q.push(Start);vis[Start]=true;
     while(!Q.empty())
     {
         t=Q.front();
         Q.pop();
         vis[t]=false;
         for(int i=last[t];i;i=next[i])
             if(dis[y[i]]>dis[t]+z[i])
             {
                 dis[y[i]]=dis[t]+z[i];
                 if(vis[y[i]]==false)
                 {
                      vis[y[i]]=true;
                      Q.push(y[i]);
                 }
             }
     }
}
void _solve()
{
     for(int i=1;i<=N;i++)           //求出scc 
         if(!vis[i])
             _DFS1(i);
     memset(vis,sizeof(vis));
     for(int i=N;i;i--)
         if(!vis[list[i]])
         {
             scc++;
             _DFS2(list[i]);
         }
     for(int i=1;i<=M;i++)           //重新构图 
         if(loc[xt[i]]!=loc[yt[i]])
         {
             tot++;
             x[tot]=loc[xt[i]];
             y[tot]=loc[yt[i]];
             z[tot]=zt[i];
             next[tot]=last[x[tot]];
             last[x[tot]]=tot;
         }
     for(int i=1;i<=scc;i++)
          dis[i]=INF;
     _SPFA(loc[1]);       //单源最短路 
     printf("%dn",dis[loc[N]]);
}
int main()
{
    _init();
    _solve();
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!