首页 > 搜索 > BFS搜索 > HDU 4171-Paper Route-BFS-[解题报告]HOJ
2015
05-23

HDU 4171-Paper Route-BFS-[解题报告]HOJ

Paper Route

问题描述 :

As a poor, tuition-ridden student, you’ve decided to take up a part time job as a paperboy/papergirl.
You’ve just been handed your paper route: a set of addresses (conveniently labelled 1 to N).

Every morning, you start at the newspaper office (which happens to be address number 0). You have to plan a route to deliver a newspaper to every address – and you also want to get to class right after you’re done.
Conveniently, there are only N roads in your area connecting the addresses, and each of them takes a known time to traverse.
Also, you’ve precalculated the time it takes to get to Waterloo campus from each address, including the newspaper office (through some combination of biking, busing, or hitching a ride).
How soon can you be done delivering papers and be in your seat at school?

输入:

Input consists of a number of cases, for each case:
First, there will be a single integer N (the number of addresses, 1 ≤ N ≤ 100,000).
Next, there will be N+1 lines, each with an integer ci (starting with i = 0, 0 ≤ ci ≤ 1,000,000,000), the time it takes to get from location i to campus.
Finally, the input will contain N lines, each with three integers a, b, c (0 ≤ a, b ≤ N, a != b, 0 ≤ c ≤ 1,000). Each of these lines describes a road between locations a and b taking c minutes to traverse.
It is guaranteed that you will be able to reach all the addresses. (Remember that location 0 is the newspaper office.)

输出:

Input consists of a number of cases, for each case:
First, there will be a single integer N (the number of addresses, 1 ≤ N ≤ 100,000).
Next, there will be N+1 lines, each with an integer ci (starting with i = 0, 0 ≤ ci ≤ 1,000,000,000), the time it takes to get from location i to campus.
Finally, the input will contain N lines, each with three integers a, b, c (0 ≤ a, b ≤ N, a != b, 0 ≤ c ≤ 1,000). Each of these lines describes a road between locations a and b taking c minutes to traverse.
It is guaranteed that you will be able to reach all the addresses. (Remember that location 0 is the newspaper office.)

样例输入:

2
1
3
4
0 1 1
0 2 2

样例输出:

7

        题目意思是给N个点,然后还有一个办公室。下面N+1行输入从办公室(即0号)开始每个到学校的距离,然后N行,正好是棵树,输入这棵树以及权值。要求遍历树上每一点然后到学校的最短的那个距离。算法是首先存下每个点到办公室的点,即把办公室的点看为根,然后通过bfs求得每个点到根的距离,然后把树的总距离求出,因为只要不是终点到根的路径,都是需要走两次的,所以取个min(total*2 – i->0 + i->school)就是答案了。用dfs做TLE了,因为好久没写bfs了,代码其搓无比,看来要多练练了=。=


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;

#define inf 2000000000
struct point
{
	vector<pair<int,int> > v;
};

int school[100005];
int zero[100005];
int biaoji[100005];

/*void dfs(int now,int val,vector<point> v)//TLE
{
	int i;
	for(i=0;i<v[now].v.size();i++)
	{
		if(biaoji[v[now].v[i].first]) continue;
		zero[v[now].v[i].first]=v[now].v[i].second+val;
		biaoji[v[now].v[i].first]=1;
		dfs(v[now].v[i].first,zero[v[now].v[i].first],v);
	}
}*/

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		memset(biaoji,0,sizeof(biaoji));
		zero[0]=0;
		int i,j;
		for(i=0;i<n+1;i++)
			scanf("%d",&school[i]);
		vector<point> v(n+1);
		int total=0;
		for(i=0;i<n;i++)
		{
			int a,b,val;
			scanf("%d%d%d",&a,&b,&val);
			pair<int,int> t,tt;
			t.first=b;tt.first=a;
			t.second=val;tt.second=val;
			v[a].v.push_back(t);
			v[b].v.push_back(tt);
			total+=val;
		}
		queue<pair<int,int> > qu;
		int sum=0;
		biaoji[0]=1;
		while(1)
		{
			if(sum==0)
			{
				for(i=0;i<v[0].v.size();i++)
				{
					//v[0].v[i].second+=zero[0];
					qu.push(v[0].v[i]);
					sum=1;
				}
			}
			else
			{
				pair<int,int> t=qu.front();
				zero[t.first]=t.second;
				biaoji[t.first]=1;
				qu.pop();
				for(i=0;i<v[t.first].v.size();i++)
				{
					if(biaoji[v[t.first].v[i].first]) continue;
					v[t.first].v[i].second+=t.second;
					qu.push(v[t.first].v[i]);
				}
			}
			if(qu.empty()) break;
		}
		//dfs(0,0,v);
		total*=2;
		int min=inf;
		for(i=0;i<n+1;i++)
		{
			if(total-zero[i]+school[i]<min) min=total-zero[i]+school[i];
		}
		printf("%d\n",min);
	}
}

复杂度就是BFS的复杂度,其实按理讲就是O(N),查询复杂度会高一点,现在都不会算复杂度了。。。。

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qiueji/article/details/7409259


, ,
  1. 卧槽 你是刚才那个人么? 怎么来了一无可奉告? 能回答我无可奉告什么意思么?我就知道你又要说回答不回答是你的自由 ….

  2. 卧槽 你是刚才那个人么? 怎么来了一无可奉告? 能回答我无可奉告什么意思么?我就知道你又要说回答不回答是你的自由 ….

  3. 卧槽 你是刚才那个人么? 怎么来了一无可奉告? 能回答我无可奉告什么意思么?我就知道你又要说回答不回答是你的自由 ….

  4. 卧槽 你是刚才那个人么? 怎么来了一无可奉告? 能回答我无可奉告什么意思么?我就知道你又要说回答不回答是你的自由 ….

  5. 卧槽 你是刚才那个人么? 怎么来了一无可奉告? 能回答我无可奉告什么意思么?我就知道你又要说回答不回答是你的自由 ….

  6. 卧槽 你是刚才那个人么? 怎么来了一无可奉告? 能回答我无可奉告什么意思么?我就知道你又要说回答不回答是你的自由 ….

  7. 恭喜小豆~~请客神马的就不去凑热闹了喜欢小豆!!!小豆加油!!!——和小豆有一样的圣诞节愿望在这里说一句啦喵,该死的黑色星期二,整个下午都不停地在做卷子好像不太温暖也就这样撒小豆要开开心心的哟~~