首页 > ACM题库 > HDU-杭电 > HDU 4396-More lumber is required-最短路径-[解题报告]HOJ
2015
05-24

HDU 4396-More lumber is required-最短路径-[解题报告]HOJ

More lumber is required

问题描述 :

“More lumber is required” When the famous warcrafts player Sky wants to build a Central Town, he finds there is not enough lumber to build his Central Town. So he needs to collect enough lumber. He lets farmer John to do this work.
  There are several Sawmills have already been built in the world, around them are large forests. Sawmills are connected by bidirectional roads (a sawmill can be connected to itself). When he passes a road, he will get 10 lumber and consume a certain time. Sky needs K lumber. So John needs collect as least K lumber.
  Sawmills are labeled from 1 to N. John initiates at Sawmill S. When he finishes his work, Sky gives him another work: arrive at Sawmill T, and build the Central Town. John needs to design his route carefully because Sky wants to build this Central Town as early as possible. He turns you for help. Please help him calculate the minimum time he needs to finish this work (collect enough lumber and build the Central Town). If impossible just print -1.
  You can read the Sample Input and Output for more information.

输入:

There are multiply test cases, in each test case:
The first line is two integers N (1<=N<=5000), M (0<=M<=100000) represent the number of sawmills and the number of the roads.
The next M line is three integers A B C (1<=A, B<=N; 1<=C<=100), means there exists a road connected Ath sawmill and Bth sawmill, and pass this road will cost C time.(The sawmills are labeled from 1 to N).
The last line is three integers S T K (1<=S, T<=N; 0<=K<=500), as mentioned as description.

输出:

There are multiply test cases, in each test case:
The first line is two integers N (1<=N<=5000), M (0<=M<=100000) represent the number of sawmills and the number of the roads.
The next M line is three integers A B C (1<=A, B<=N; 1<=C<=100), means there exists a road connected Ath sawmill and Bth sawmill, and pass this road will cost C time.(The sawmills are labeled from 1 to N).
The last line is three integers S T K (1<=S, T<=N; 0<=K<=500), as mentioned as description.

样例输入:

4 4
1 2 1
2 3 2
1 3 100
3 4 1
1 3 50

样例输出:

7

/*
分析:
    每条边可重复通过,求至少经过K次边的最短路。

                                    2012-10-14
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"queue"
using namespace std;
int s,e,LIMIT;
struct node
{
	int index;
};
struct Eage
{
	int from,to,len;
	int next;
}eage[200011];
int tot,head[5011];
int dis[5011][55];
void add(int a,int b,int len)
{
	eage[tot].from=a;
	eage[tot].to=b;
	eage[tot].len=len;
	eage[tot].next=head[a];
	head[a]=tot++;
}
void SPFA()
{
	int l,j;
	int flag;
	int hash[5011];
	queue<node>q;
	node now,next;

	memset(hash,0,sizeof(hash));
	memset(dis,127,sizeof(dis));
	now.index=s;
	dis[s][0]=0;
	q.push(now);
	hash[s]=1;

	while(!q.empty())
	{
		now=q.front();
		q.pop();
		hash[now.index]=0;
		for(j=head[now.index];j!=-1;j=eage[j].next)
		{
			flag=0;
			dis[now.index][LIMIT]=dis[now.index][LIMIT]>dis[now.index][LIMIT+1]?dis[now.index][LIMIT+1]:dis[now.index][LIMIT];
			for(l=0;l<=LIMIT;l++)
			{
				if(dis[now.index][l]+eage[j].len<dis[eage[j].to][l+1])
				{
					flag=1;
					dis[eage[j].to][l+1]=dis[now.index][l]+eage[j].len;
				}
			}
			if(flag && !hash[eage[j].to])
			{
				next.index=eage[j].to;
				q.push(next);
				hash[next.index]=1;
			}
		}
	}
}
int main()
{
	int n,m;
	int a,b,c;
	int ans;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		memset(head,-1,sizeof(head));
		tot=0;
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
		}
		scanf("%d%d%d",&s,&e,&LIMIT);
		LIMIT=LIMIT/10+(LIMIT%10==0?0:1);

		SPFA();

		ans=1111111111;
		ans=ans>dis[e][LIMIT]?dis[e][LIMIT]:ans;
		if(ans==1111111111)	printf("-1\n");
		else				printf("%d\n",ans);
	}
	return 0;
}

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

参考:http://blog.csdn.net/ice_crazy/article/details/8069521