题目大意
给你一个图，从0出发可以到达每个点，问从0出发访问每条边的花费，图中如果一些点可以相互到达的话，那么这些点之间的边的花费可以忽略不计。
解题思路
从相互到达的点的花费可以忽略这点来看，显然是让算强连通分量的。对于同一个强连通分量，只需要找一个最短的边，这个边连接另外一个强连通分量与这个强连通分量中的一个点，最后的答案就是它们的累加和。PS：0号点是出发点，并且能到达所有点，所以入度必定为0，不需要计算到达0号点所在强连通分量需要的花费(也算不出来)。
代码
vector<P> e[maxn];
int n, m, d[maxn];
int low[maxn], dfn[maxn], dn, scc[maxn], sc, sk[maxn], tp;
void tarjan(int u) {
dfn[u] = low[u] = ++dn;
sk[++tp] = u;
for (auto v : e[u]) {
if (!dfn[v.second]) {
tarjan(v.second);
low[u] = min(low[u], low[v.second]);
}
else if (!scc[v.second]) low[u] = min(low[u], dfn[v.second]);
}
if (dfn[u]==low[u]) {
++sc;
while(true) {
int v = sk[tp--];
scc[v] = sc;
if (u==v) break;
}
}
}
int main() {
while(~scanf("%d%d", &n, &m)) {
dn = sc = tp = 0;
for (int i = 0; i<n; ++i) e[i].clear();
zero(low); zero(dfn); zero(scc); zero(sk); INF(d);
for (int i = 0, u, v, w; i<m; ++i) {
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(w, v);
}
for (int i = 0; i<n; ++i)
if (!dfn[i]) tarjan(i);
for (int i = 0; i<n; ++i)
for (auto v : e[i])
if (scc[i]!=scc[v.second]) d[scc[v.second]] = min(d[scc[v.second]], v.first);
ll sum = 0;
for (int i = 1; i<=sc; ++i)
if (d[i]!=INF) sum += d[i]; //因为0号点是出发点并且能够到达所有点所以到达0号点的花费肯定是INF
printf("%lld
", sum);
}
return 0;
}