题目链接：http://codeforces.com/gym/100676/attachments
题意：
有 n 个点，m 条边，图中，边强连通分量之间可以直达，即距离为 0 ，找一个点当做首都，其他点到首都的最大距离最小。
参考：http://www.cnblogs.com/ost-xg/p/6395100.html
仔细研究了大佬的思路，很牛逼，但是也有一点细节遗漏了，但是还是能AC，interesting；
分析：
边双连通：条件比点双连通松一点，体现在程序中，就是存在一个子节点能到达的最早祖先在父节点之后（没有等于）；这样桥就找到了，然后再去找边双连通分量——dfs，从一个点出发，是桥就不是同一个边双连通分量；
这样就把题目中的边双连通分量找出来了；
然后缩点重新建图ed的边集！！！（遍历每一条边，是桥就加上来，大佬的这里多加了哦）
此时，怎么选首都呢？
其实，现在图已经是一棵树了，遍历每一个点跑最短路是傻逼行为；
先找到树的直径，首都一定在这条直径上，枚举直径上的点，最远的，不过是直径上的两个部分；
#include <bits/stdc++.h> using namespace std; const int maxn = ;
const long long inf = 1e15 + ; struct Edge
{
long long u, v, c;
} e[maxn<<];
struct Ed
{
long long v, c;
}; int n, m, low[maxn], pre[maxn], tim, ebcc_cnt, du[maxn];
long long k, len, dis[maxn][];
vector<int> G[maxn];
vector<Ed> ed[maxn];
int isbri[maxn<<];
bool vis[maxn]; void init()
{
ebcc_cnt = tim = ;
for (int i = ; i <= n; i++) G[i].clear();
memset(isbri, , sizeof(isbri));
memset(pre, , sizeof(pre));
memset(du, , sizeof(du));
} void tarjan(int u, int fa)
{
low[u] = pre[u] = ++tim;
for (int i = ; i < G[u].size(); i++)
{
int tmp = G[u][i];
int v = e[tmp].v;
if (!pre[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > pre[u])
isbri[tmp] = isbri[tmp^] = true; //标记为桥
}
else if (fa != v)
low[u] = min(low[u], pre[v]);
}
} void dfs(int u)
{
pre[u] = ebcc_cnt;
for (int i = ; i < G[u].size(); i++)
{
int tmp = G[u][i];
if (isbri[tmp]) continue;
int v = e[tmp].v;
if (pre[v]) continue;
dfs(v);
}
} void find_ebcc()
{
tarjan(, -);
memset(pre, , sizeof(pre));
for (int i = ; i <= n; i++)
{
if (!pre[i])
{
ebcc_cnt++;
dfs(i);
}
}
} void BFS(int s, int ca)
{
memset(vis, , sizeof(vis));
queue<Ed> q;
q.push((Ed)
{
s,
});
vis[s] = ;
while (q.size())
{
Ed tmp = q.front();
q.pop();
dis[tmp.v][ca] = tmp.c;
for (int i = ; i < ed[tmp.v].size(); i++)
{
Ed xx = ed[tmp.v][i];
if (!vis[xx.v])
{
vis[xx.v] = ;
q.push((Ed)
{
xx.v, xx.c + tmp.c
});
}
}
}
} void dfs_len(int x, int fa, long long dep)
{
if (dep > len)
{
k = x;
len = dep;
}
for (int i = ; i < ed[x].size(); i++)
{
Ed tmp = ed[x][i];
if (tmp.v == fa) continue;
dfs_len(tmp.v, x, dep + tmp.c);
}
} int main()
{
int t = ;
cin >> t; while (t--)
{
cin >> n >> m;
init();
for (int i = ; i <= m; i++)
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
e[i<<|].u = u, e[i<<|].v = v, e[i<<|].c = c;
e[i<<].u = v, e[i<<].v = u, e[i<<].c = c;
G[u].push_back(i<<|);
G[v].push_back(i<<);
}
find_ebcc();
int tot = m<<|;
for (int i = ; i <= ebcc_cnt; i++) ed[i].clear();
for (int i = ; i <= tot; i += )
{
if (isbri[i])
{
int u = e[i].v, v = e[i].u;
ed[pre[u]].push_back((Ed)
{
pre[v], e[i].c
});
ed[pre[v]].push_back((Ed)
{
pre[u], e[i].c
});
}
}
len = -;
dfs_len(, -, );
int st = k;
len = -;
dfs_len(st, -, );
BFS(st, );
BFS(k, );
long long inx = n + , dd = inf;
for (int i = ; i <= n; i++)
{
int pr = pre[i];
if (dis[pr][] + dis[pr][] != len) continue;
long long tmp = max(dis[pr][], dis[pr][]);
if (tmp < dd)
{
inx = i;
dd = tmp;
}
}
printf("%lld %lld\n",inx,dd);
}
return ;
}