首页 > ACM题库 > HDU-杭电 > HDU 3986-Harry Potter and the Final Battle-最短路径-[解题报告]HOJ
2015
04-14

HDU 3986-Harry Potter and the Final Battle-最短路径-[解题报告]HOJ

Harry Potter and the Final Battle

问题描述 :

The final battle is coming. Now Harry Potter is located at city 1, and Voldemort is located at city n. To make the world peace as soon as possible, Of course, Harry Potter will choose the shortest road between city 1 and city n. But unfortunately, Voldemort is so powerful that he can choose to destroy any one of the existing roads as he wish, but he can only destroy one. Now given the roads between cities, you are to give the shortest time that Harry Potter can reach city n and begin the battle in the worst case.

输入:

First line, case number t (t<=20).
Then for each case: an integer n (2<=n<=1000) means the number of city in the magical world, the cities are numbered from 1 to n. Then an integer m means the roads in the magical world, m (0< m <=50000). Following m lines, each line with three integer u, v, w (u != v,1 <=u, v<=n, 1<=w <1000), separated by a single space. It means there is a bidirectional road between u and v with the cost of time w. There may be multiple roads between two cities.

输出:

First line, case number t (t<=20).
Then for each case: an integer n (2<=n<=1000) means the number of city in the magical world, the cities are numbered from 1 to n. Then an integer m means the roads in the magical world, m (0< m <=50000). Following m lines, each line with three integer u, v, w (u != v,1 <=u, v<=n, 1<=w <1000), separated by a single space. It means there is a bidirectional road between u and v with the cost of time w. There may be multiple roads between two cities.

样例输入:

3
4
4
1 2 5
2 4 10
1 3 3
3 4 8
3
2
1 2 5
2 3 10
2
2
1 2 1
1 2 2

样例输出:

15
-1
2

/*
分析:
    数组开小,让我WA了两天- -III,血的教训。。。
    先求最短路径,储存路径,然后枚举路径上的边,
一个个删,并求当前最短路径,求得的这些最短路径中,
最大的就是答案了。

                                              2012-07-27
*/

#include"stdio.h"
#include"string.h"


struct A
{
	int dis;
	int pre;
	int pre_len;
	int total;
	int mem[1011];
	int len[1011];
}E[1011];
int n;


int SPFA()
{
	int k,key;
	int queue[2222];
	int i;
	int hash[1011];


	memset(hash,0,sizeof(hash));
	key=1;
	k=0;
	queue[0]=1;
	hash[1]=1;


	while(k<key)
	{
		for(i=0;i<E[queue[k]].total;i++)
		{
			if(E[queue[k]].dis+E[queue[k]].len[i]<E[E[queue[k]].mem[i]].dis)
			{
				E[E[queue[k]].mem[i]].pre=queue[k];
				E[E[queue[k]].mem[i]].pre_len=E[queue[k]].len[i];
				E[E[queue[k]].mem[i]].dis=E[queue[k]].dis+E[queue[k]].len[i];
				if(!hash[E[queue[k]].mem[i]])
				{
					hash[E[queue[k]].mem[i]]=1;
					queue[key++]=E[queue[k]].mem[i];
				}
			}
		}
		hash[queue[k++]]=0;
	}
	return E[n].dis;
}
int main()
{
	int T;
	int m;
	int i,l;
	int a,b,c;
	int ans;
	int des[1011],des2[1011],len,k;
	int temp;
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);


		for(i=1;i<=n;i++)
		{
			E[i].total=0;
			E[i].dis=1111111111;
			E[i].pre=i;
		}
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&c);
			E[a].mem[E[a].total]=b;
			E[a].len[E[a].total++]=c;
			E[b].mem[E[b].total]=a;
			E[b].len[E[b].total++]=c;
		}


		E[1].dis=0;
		temp=SPFA();
		
		k=0;
		temp=n;
		while(E[temp].pre!=temp)
		{
			des2[k]=E[temp].pre_len;
			des[k++]=temp;
			temp=E[temp].pre;
		}
		des[k++]=temp;


		ans=-1;
		for(i=0;i<k-1;i++)
		{
			a=des[i];
			b=des[i+1];
			len=des2[i];


			for(l=0;l<E[a].total;l++)	if(E[a].mem[l]==b && E[a].len[l]==len)	break;
			for(;l<E[a].total-1;l++)	{E[a].mem[l]=E[a].mem[l+1];E[a].len[l]=E[a].len[l+1];}
			E[a].total--;
			for(l=0;l<E[b].total;l++)	if(E[b].mem[l]==a && E[b].len[l]==len)	break;
			for(;l<E[b].total-1;l++)	{E[b].mem[l]=E[b].mem[l+1];E[b].len[l]=E[b].len[l+1];}
			E[b].total--;


			for(l=2;l<=n;l++)	E[l].dis=1111111111;
			E[1].dis=0;


			temp=SPFA();
			if(temp>ans)	ans=temp;


			E[a].mem[E[a].total]=b;
			E[a].len[E[a].total++]=len;
			E[b].mem[E[b].total]=a;
			E[b].len[E[b].total++]=len;
		}


		if(ans==1111111111)	printf("-1\n");
		else				printf("%d\n",ans);
	}
	return 0;
}

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

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


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧