BFS-BZOJ-1602-[Usaco2008 Oct]牧场行走

2023-10-17 07:18

本文主要是介绍BFS-BZOJ-1602-[Usaco2008 Oct]牧场行走,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

N头牛(2<=n<=1000)别人被标记为1到n,在同样被标记1到n的n块土地上吃草,第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走,第i条边连接第Ai,Bi块牧场,第i条边的长度是Li(1<=Li<=10000)。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况,所以说这是一棵树。 这些奶牛是非常喜欢交际的,经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
Input

*第一行:两个被空格隔开的整数:N和Q

*第二行到第n行:第i+1行有两个被空格隔开的整数:AI,BI,LI

*第n+1行到n+Q行:每一行有两个空格隔开的整数:P1,P2,表示两头奶牛的编号。
Output

*第1行到第Q行:每行输出一个数,表示那两头奶牛之间的距离。
Sample Input
4 2

2 1 2

4 3 2

1 4 3

1 2

3 2

Sample Output
2

7


题解:
其实就是一个对树的BFS,当然还有更简单的做法,我选了无脑的搜搜搜。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 1005
#define INF 0x7fffffff
using namespace std;
int n,q;
bool vis[MAXN];
typedef struct edge
{int v,cost;edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
}Edge;
vector<Edge>E[MAXN];
void addedge(int u,int v,int cost)
{E[u].push_back(edge(v,cost));E[v].push_back(edge(u,cost));
}
typedef struct qnode
{int num;long long int total;qnode(int _num=0,long long int _total=0):num(_num),total(_total){}
}Qnode;
queue<Qnode>Q;
long long int bfs(int u,int v)
{Qnode now,tmp;memset(vis,0,sizeof(vis));while(!Q.empty()) Q.pop();Q.push(qnode(u,0));while(!Q.empty()){now=Q.front();Q.pop();if(now.num==v)return now.total;for(int i=0;i<E[now.num].size();i++){if(vis[E[now.num][i].v]==0){tmp.num=E[now.num][i].v;tmp.total=now.total+E[now.num][i].cost;vis[E[now.num][i].v]=1;Q.push(tmp);}}}return 0;
}
int main()
{int a,b,l;cin >> n >> q;for(int i=1;i<n;i++){scanf("%d%d%d",&a,&b,&l);addedge(a,b,l);}for(int i=1;i<=q;i++){scanf("%d%d",&a,&b);cout << bfs(a,b) << endl;}return 0;
}

这篇关于BFS-BZOJ-1602-[Usaco2008 Oct]牧场行走的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/223814

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接: http://acm.hdu.edu.cn/showproblem.

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接:点击打开链接 C. 题目链接:点击打开链接 解题思路: 对于给定的字符串,取出现次数最多的字母(可以同时有多个)。由这些字母组成长度为n的字符串,求有多少种组合。最后用数学知识即可。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <climits>

java常用算法之字梯(广度优先搜索bfs)

<span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;">给定2个单词(start</span><span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;">和