学步园

开始我直接枚举删边 就超时，后来想了下，只要枚举最短路径上的边删除就行了。。。改了下 就AC了

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
const int inf=999999999;
int n,m,cnt,a,b,l,dis[1010],in[1010],head[1010],mp[1010][1010];
set<int>vt;
struct EDGE
{
	int y,l,nxt;
}edge[1000010];
void add(int x,int y,int l)
{
	edge[cnt].y=y;
	edge[cnt].l=l;
	edge[cnt].nxt=head[x];
	head[x]=cnt++;
}
void addedge(int x,int y,int l)
{
	add(x,y,l);
	add(y,x,l);
}
int spfa(int f)
{
	fill(dis,dis+n+1,inf);
	memset(in,0,sizeof(in));
	queue<int>q;
	q.push(1);
	in[1]=1;
	dis[1]=0;
	while(!q.empty())
	{
		int s=q.front();
		q.pop();
		in[s]=0;
		for(int j=head[s];j!=-1;j=edge[j].nxt)
		{
			int y=edge[j].y,l=edge[j].l;
			if((j==f)||((j^1)==f))continue;
			if(dis[y]>dis[s]+l)
			{
				dis[y]=dis[s]+l;
				if(!in[y])
				{
					in[y]=1;
					q.push(y);
				}
			}
		}
	}
	return dis[n];
}
void dfs(int x)
{
	if(x==1)return;
	for(int j=head[x];j!=-1;j=edge[j].nxt)
	{
		int y=edge[j].y,l=edge[j].l;
		if(dis[y]+l==dis[x])
		{
			vt.insert(j);
			dfs(y);
		}
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		cnt=0;
		memset(head,-1,sizeof(head));
		memset(mp,0,sizeof(mp));
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&l);
			if(a==b)continue;
			if(mp[a][b]==0)
			{
				mp[a][b]=mp[b][a]=l;
			}
			else
				mp[a][b]=min(mp[a][b],l);
		}
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				if(mp[i][j])
				{
					addedge(i,j,mp[i][j]);
				}
			}
		int ans=0;
		spfa(-1);
		vt.clear();
		dfs(n);
		for(set<int>::iterator it=vt.begin();it!=vt.end();++it)
		{
			ans=max(spfa(*it),ans);
		}
		printf("%d\n",ans);
	}
	return 0;
}