HDU3986 Harry Potter and the Final Battle最短路

Harry Potter and the Final Battle

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 294 Accepted Submission(s): 97

Problem Description 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.

Input 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.

Output Each case per line: the shortest time to reach city n in the worst case. If it is impossible to reach city n in the worst case, output “-1”.

Sample Input 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

Sample Output 15

-1

2

Author [email protected]

Source 2011 Multi-University Training Contest 15 - Host by WHU

Recommend lcy   先求一次最短路，枚舉删除最短路上的邊再求最短路，取最大值即為答案。 這麼簡單的一道題竟然TLE+WA無數次。。。 我的錯誤： 1.第一次用dij而不是用spfa，估計是導緻TLE的原因 2.答案取最大值就不能用-1來更新答案，應該用inf更新   代碼：  

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 999999999
using namespace std;

int t,n,m,flag,num,adj[1005],low[1005],pre[1005],q[1005];
struct edge
{
	int u,v,w,f,pre;
}e[200005];
void insert(int u,int v,int w)
{
	e[num].u=u;
	e[num].v=v;
	e[num].w=w;
	e[num].f=1;
	e[num].pre=adj[u];
	adj[u]=num++;
}
int spfa()
{
	int i,x,v,w,f[1005]={0},head=0,tail=0;
	for(i=1;i<=n;i++)
		low[i]=inf;
	low[1]=0;
	q[++tail]=1;
	while(head!=tail)
	{
		x=q[head=(head+1)%1005];
		f[x]=0;
		for(i=adj[x];~i;i=e[i].pre)
			if(e[i].f&&low[v=e[i].v]>(w=low[x]+e[i].w))
			{
				low[v]=w;
				if(flag)
					pre[v]=i;
				if(!f[v])
				{					
					f[v]=1;
					q[tail=(tail+1)%1005]=v;
				}
			}
	}
	return low[n];
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int i,j,k,u,v,w,ans=-1;
		num=0;
		memset(adj,-1,sizeof(adj));
		scanf("%d%d",&n,&m);
		while(m--)
		{
			scanf("%d%d%d",&u,&v,&w);
			insert(u,v,w);
			insert(v,u,w);
		}
		memset(pre,-1,sizeof(pre));
		flag=1;
		spfa();
		flag=0;
		i=n;
		while(pre[i]!=-1)
		{
			j=pre[i];
			e[j].f=e[j^1].f=0;
			k=spfa();
			e[j].f=e[j^1].f=1;
			if(k>ans)
				ans=k;
			i=e[j].u;
		}
		if(ans<inf)
			printf("%d\n",ans);
		else
			puts("-1");
	}
}