题目背景
小\(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 21 2 12 3 1
输出样例#1：
2
输入样例#2：
5 51 2 12 3 63 4 14 2 13 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#include #include #include #include #include #define maxn 200001using 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 q1;priority_queue 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\n",dis[n]); return 0;}