hdu 3986 Harry Potter and the Final Battle

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3986

题意：给出一个无向图，Harry Potter的目的是从1到n，而Voldemort为了阻止他，使用魔法毁掉了图中的一条边，

问最坏情况下Harry要走的最短路是多少。

注意：两点间可以能存在多条路，而且路是双向的，找到最短路后枚举边，求的最短路中最长的那条即为所求，

#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn = 1005;
const int INF = 1<<30;
struct node
{
	int v,w;
	struct node *next;
}*head[maxn],edge[50005*2],*p;
int dis[maxn],per[maxn],n;
bool vis[maxn];
queue<int>que;
void spfa(bool flg)
{//求起点到终点的最短路
	for(int i = 1; i <= n; i++)
		dis[i] = INF;
	memset(vis,false,sizeof(vis));
	dis[1] = 0;
	vis[1] = true;
	que.push(1);
	while( !que.empty() )
	{
		int now = que.front();
		que.pop();
		vis[now] = false;
		for(p = head[now]; p ; p = p->next)
		{
			if(dis[p->v] > dis[now] + p->w)
			{
				if(flg)//flg为真表示没有删除边，为假表示求删除某条边后求最短路。
					per[p->v] = now;
				dis[p->v] = dis[now] + p->w;
				if(!vis[p->v])
				{
					vis[p->v] = true;
					que.push(p->v);
				}
			}
		}
	}
}

int main()
{
	int t,m,i,u,v,w;
	scanf("%d",&t);
	while( t-- )
	{
		scanf("%d%d",&n,&m);
		for(i = 1; i <= n; i++)
			head[i] = NULL;
		p = edge;
		while( m-- )
		{
			scanf("%d%d%d",&u,&v,&w);
			p->v = v;p->w = w;
			p->next = head[u];
			head[u] = p++;
			
			p->v = u;p->w = w;
			p->next = head[v];
			head[v] = p++;
		}
		memset(per,-1,sizeof(per));
		spfa(true);
		
		int max = -1;
		if(dis[n] != INF)//存在最短路
		{
			
			node *q1,*q2;
			for(i = n; per[i] != -1; i = per[i])
			{
				int min = INF;
				q1 = q2 = NULL;
				//找i和per[i]间距离最短的边
				for(p = head[per[i]] ; p ; p = p->next)
				{
					if(p->v == i && p->w < min)
					{
						min = p->w;
						q1 = p;
					}
				}

				for(p = head[i] ; p ; p = p->next)
				{
					if(p->v == per[i] && p->w == min)
					{
						q2 = p;
						break;
					}
				}
				//去除边，
				q1->w = q2->w = INF;
				spfa(false);
				//当去除某条边后没有到终点的路径，则结束循环。
				if(dis[n] >= INF)
					break;
				if(dis[n] > max)
					max = dis[n];
				//将去除的边还原
				q1->w = q2->w = min;
			}
		}
		printf("%d\n",max);
	}
	return 0;
}