和往常一样，继续从题目引入
树上奶牛
（tree.cpp）
【题目描述】
农夫John的奶牛不是住在地上而是住在树上的QWQ。
奶牛之间需要串门，不过在串门之前他们会向John询问距离的大小。可是John的产业有点大奶牛的个数有点多，这让农夫John感到头疼，你能帮助他吗？
Ps：这里提到的树为OI界的[树]，即无向无环图。而且因为一棵树的承载量是有限的，所以所有的奶牛可能会分布在不同的树上，即OI界的[森林]。
【文件格式】
输入文件：
第一行两个整数n m，分别表示n个结点m条边。
以下m行，每行三个整数u,v,w，分别表示u,v之间有一条距离为w的树边。
第m+2行一个整数q，表示询问的个数。
以下q行，每行两个整数u,v，表示奶牛要询问u,v之间的距离。
输出文件：
输出q行，每行对应一个询问输出答案。如果u,v不处于同一棵树上，请回答-1。
【样例数据】
Input（tree.in）
5 3
1 3 5393
3 4 2845
4 2 3757
3
1 4
1 2
1 5
Output (tree.out)
8238
11995
-1
【数据约束】
对于30%的数据，n<=1000 , m<=1000 , q<=10000。
对于100%的数据，n<=10000,m<=40000,q<=100000。
[Hint] 对于所有数据皆随机生成。
这道题目打眼看过去就知道是个图上的最短路径问题，查询某个点是否与另一个点相连，如果相连输出最短路径，否则的话输出“-1”。
看上面我用黄色标出的部分，数据范围略大，这里我是用的结构体存边和边权：
struct node
{
int weight;
int one;
int two;
};
node a[40000];
这道题并不是简单的图上的最短路问题，它有一个查询的过程，这里我是用的并查集判断两个点是否有链接，如果是的话就用贝尔曼-福德求最短路，如果否的话就直接输出“-1”：
int father[10000];
//判断是否连接
int find(int x)
{
if(father[x]!=x) return find(father[x]);
else return x;
}
if(find(u)==find(v))
{
sou(u,v);
}
else
{
cout<<"-1";
}
下面上代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct node
{
int weight;
int one;
int two;
};
node a[40000];
int father[10000];
int n,m;
int u,v,w;
int q;
void sou(int x,int y)
{
long long dis[n+1];
for(int i=1;i<=n+1;i++)
{
dis[i]=0x7ffffff;
}
dis[x]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(dis[a[j].one]+a[j].weight<dis[a[j].two]) dis[a[j].two]=dis[a[j].one]+a[j].weight;
if(dis[a[j].two]+a[j].weight<dis[a[j].one]) dis[a[j].one]=dis[a[j].two]+a[j].weight;
}
}
cout<<dis[y]<<endl;
}
int find(int x)
{
if(father[x]!=x) return find(father[x]);
else return x;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
father[i]=i;
}
for(int i=1;i<=m;i++)
{
cin>>u>>v;
a[i].one=u;
a[i].two=v;
father[u]=v;
//father[v]=u;
cin>>a[i].weight;
}
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>u>>v;
if(find(u)==find(v))
{
sou(u,v);
}
else
{
cout<<"-1";
}
}
}
注：还没有测评，用的贝尔曼福德q大的时候可能会有点超时，可以再用SPFA试一下。。。
原文：http://www.cnblogs.com/zhangone/p/5081577.html