P2169 正则表达式 在Internet网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在A到B的连接不一定存在B到A的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。

现在小Z告诉你整个网络的构成情况，他希望知道从他的电脑（编号为1），到小X的电脑（编号为n）所需要的最短传输时间。

对于100%的数据，1\leq n\leq200000, 1\leq m\leq 1000000

解题思路：

Tarjan 缩点 + SPFA/DP

首先观察数据范围，显然这么大的 n,m ，直接跑 O(nm) 的 SPFA 会炸掉。

观察题面，发现如果有 x 和 y 构成一个环（处在同一个 SCC 中），那么他们之间的边长度为 0

这启发我们可以用缩点后再来跑 SPFA ，但是这样的复杂度是不够严谨的，最坏情况下仍旧是 O(nm) 的，只是由于这题水所以可以过。

代码：

SPFA 版本 

#include <cstdio>
#include <cctype>
#include <cmath>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;
inline int read() {
    char v = getchar();int x = 0,f = 1;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
    return x * f;
}
const int N = 10010;
const int M = 5000010;

int to[M],hd[N],nxt[M],tot,edg[M];
inline void add(int u,int v,int w) {to[++tot] = v;edg[tot] = w;nxt[tot] = hd[u];hd[u] = tot;}

inline int min(int x,int y) {return x<y?x:y;}
inline int max(int x,int y) {return x>y?x:y;}

using std::stack;

int dfn[N],low[N],ins[N],cnt,num,c[N],n,m,p[N],f[N];
stack <int> s;

void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    s.push(x);ins[x] = 1;
    for (int i = hd[x];i;i = nxt[i]) {
        if (!dfn[to[i]]) {
            tarjan(to[i]);
            low[x] = min(low[x],low[to[i]]);
        }
        else if (ins[to[i]]) {
            low[x] = min(low[x],dfn[to[i]]);
        }
    }
    if (dfn[x] == low[x]) {
        c[x] = ++num;int y;
        do {
            y = s.top(),s.pop();
            ins[y] = 0;c[y] = num;
        }while (x != y);
    }
}

int vis[N],dis[N];

void SPFA(int s) {
    memset(dis,0x3f,sizeof(dis));
    queue <int> q;
    vis[s] = 1;dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();q.pop();
        vis[x] = 0;
        for (int i = hd[x];i;i = nxt[i]) {
            int y = to[i],w = edg[i];
            if (c[x] == c[y]) w = 0;
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                if (!vis[y]) {
                    q.push(y);
                    vis[y] = 1;
                }
            }
        }
    }
}

int main() {
    n = read(),m = read();
    for (int i = 1;i <= m;++i) {
        int x = read(),y = read(),w = read();add(x,y,w);
    }
    for (int i = 1;i <= n;++i) if (!dfn[i]) tarjan(i);
    SPFA(1);
    printf("%d",dis[n]);
    return 0;
}