stonechina0616

题目背景

小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缩点，然后跑一遍dijkstra。

代码：

#include<cstdio> #include<algorithm> #include<vector> #include<iostream> #include<cstring> #include<stack> #include<queue> #define rep(q,p) for(int q=1;q<=p;q++) using namespace std; const int maxn=2e5+5; int dfn[maxn],low[maxn],bel[maxn],dis[maxn],cnt,scc,m,n,x,y,z; bool ins[maxn]; struct hehe { int point,num; bool operator < (const hehe & hehehe) const { if (num==hehehe.num) return hehehe.point<point; else return hehehe.num<num; } }tmp; vector<hehe>v[maxn]; stack<int>s;/* dfn表示某个点在DFS序中的位置，low表示栈中追溯到最早的点 bel表示这个点在某个强连通分量中，当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量 https://stone906229046.blog.163.com/blog/static/267075001201692894725593*/ void tarjan(int k) //tarjan缩点 { cnt++; dfn[k]=cnt,low[k]=cnt; ins[k]=true; //标记这个元素在栈中 s.push(k); for (int i=0;i<v[k].size();i++) { int tp=v[k][i].point; if (!dfn[tp]) { tarjan(tp); if (low[tp]<low[k]) low[k]=low[tp]; //更新low值 } if (ins[tp] && low[tp]<low[k]) low[k]=low[tp]; //更新low值 } if (low[k]==dfn[k]) { scc++; int tp=0; while (k!=tp) { tp=s.top(); s.pop(); ins[tp]=false; bel[tp]=scc; } } } void dijkstra(int fir) { int mnum,p=0; memset(dis,127,sizeof(dis)); dis[fir]=0; priority_queue<hehe>q; tmp.num=0; tmp.point=fir; q.push(tmp); while(!q.empty()) { tmp=q.top(); q.pop(); int k=tmp.point; for (int i=0;i<v[k].size();i++) { int tp=v[k][i].point,tnum=v[k][i].num; if (bel[tp]==bel[k]) tnum=0; if (dis[tp]>dis[k]+tnum) { dis[tp]=dis[k]+tnum; tmp.point=tp; tmp.num=dis[tp]; q.push(tmp); } } } return; } int main() { scanf("%d%d",&n,&m); rep(i,m) { scanf("%d%d%d",&x,&y,&z); tmp.num=z,tmp.point=y; v[x].push_back(tmp); } tarjan(1); dijkstra(1); cout<<dis[n]<<endl; return 0; }