思路：
这个最短路算法是想都别想了，可以看出这幅图就是树嘛，那么对于查询就是求树上两个结点最短距离。
这里就是利用LCA的tarjan离线算法。
算法的大致流程：
对于每一点u，
① ：建立以u为代表元素的集合。
② ：遍历与u相连的结点v，如果没有访问过，对与v使用Tarjan-LCA算法，结束后，将v的集合并入u的集合。
③ ：对于与u相关的询问(u,v)，如果v被访问过，则结果就是v所在集合的代表。
在这里还需要算距离，需要深度：dis<v1,v2>=dis[v1]+dis[v2]-2*dis[lca];简要说下这份代码的几个变量的作用：
vis[ ]是用来确定集合，可能存在多棵树？
pre[ ]每次存的是前驱，为什么正好在Find()过程中就他们的LCA呢？
这是因为一直在处理的是子树呀！对于结点yeye，他的son结点叫baba，结点baba有两个结点：结点sunzei，结点sunnv。
本身Tarjan就是个DFS，所以搜索的话要一直处理完子树所有，也就是处理完结点baba的所有，才会处理到结点yeye，对于当前子树而言，并查集的作用也是对于当前子树的情况，所以结点sunzei和sunnv的LCA就是baba，不是yeye。
大致感觉也能感觉粗来吧？
PS:这份代码
HDU2586 改改就过了，而且题目中的说的空行是没有的~（蜜汁怂恿贴代码嫌疑。。）
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxm=2e4+10;
const int maxn=1e4+10;
const int maxq=2e6+10;
struct Node{
int to;
int w;
int next;
}e[maxm];
int eh[maxn],dis[maxn],pre[maxn],etol,vis[maxn];
struct Query{
int to;
int index;
int next;
}qe[maxq];
int qh[maxn],ans[maxq/2],qtol;
int n,m,c;
void init()
{
etol=qtol=0;
memset(eh,-1,sizeof(eh));
memset(qh,-1,sizeof(qh));
}
void add1(int u,int v,int w)
{
e[etol].to=v;
e[etol].w=w;
e[etol].next=eh[u];
eh[u]=etol++;
}
void add2(int u,int v,int id)
{
qe[qtol].index=id;
qe[qtol].to=v;
qe[qtol].next=qh[u];
qh[u]=qtol++;
}
int Find(int u)
{
if(pre[u]!=u) pre[u]=Find(pre[u]);
return pre[u];
}
void LCA(int u,int deep,int root)
{
pre[u]=u;
dis[u]=deep;
vis[u]=root;
for(int i=eh[u];~i;i=e[i].next)
{
int v=e[i].to;
if(vis[v]==-1)
{
LCA(v,deep+e[i].w,root);
pre[v]=u;
}
}
for(int i=qh[u];~i;i=qe[i].next)
{
int v=qe[i].to;
if(vis[v]==root)
ans[qe[i].index]=dis[v]+dis[u]-2*dis[Find(v)];
}
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&c))
{
int u,v,w;
init();
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
add1(u,v,w);
add1(v,u,w);
}
for(int i=0;i<c;i++)
{
scanf("%d%d",&u,&v);
ans[i]=-1;
add2(u,v,i);
add2(v,u,i);
}
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;i++){
if(vis[i]==-1)
LCA(i,0,i);
}
for(int i=0;i<c;i++)
{
if(ans[i]==-1) puts("Not connected");
else printf("%d
",ans[i]);
}
}
return 0;
}