和往常一样,继续从题目引入
树上奶牛
(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试一下。。。