顺德网站制作案例机构/seo网站推广软件

给你一个无向图，然后找出其中的最短路，

除去最短路中的任意一条边，看最糟糕的情况下，

新的图中，第一个点到末点的最短路长度是多少。

我的做法是：

首先找出最短路，然后记录路径，

再一条一条边的删，

删一条算一下最短路长度，

之后恢复这条边，删掉下一条边继续算，

以此类推。

看之中最糟糕的情况下，最短路长度是多少，

如果是无穷大则代表最坏情况为不通，按题意输出-1即可，

否则输出最坏情况下，最短路长度。

我用spfa和链式向前星做的，

代码如下：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
bool flag;
int exp,num_dot,num_side,cnt,pd[1010],ps[1010],die[100010],dis[1010],box[1010];
struct node
{int to,next,w,co;
}side[100010];
void add(int from,int to,int w)
{side[cnt].to=to;side[cnt].w=w;side[cnt].next=box[from];box[from]=cnt++;
}
void init()
{int s,e,w;cnt=0;flag=1;memset(box,-1,sizeof(box));memset(die,0,sizeof(die));scanf("%d%d",&num_dot,&num_side);for(int i=0;i<num_side;i++){scanf("%d%d%d",&s,&e,&w);side[cnt].co=cnt+1;add(s,e,w);side[cnt].co=cnt-1;add(e,s,w);}
}
void spfa()
{int mid;bool iq[1010];queue<int>qq;memset(iq,0,sizeof(iq));memset(dis,127,sizeof(dis));dis[1]=0;qq.push(1);iq[1]=1;while(qq.size()){mid=qq.front();qq.pop();iq[mid]=0;for(int i=box[mid];i>-1;i=side[i].next)if(die[i]==0&&dis[side[i].to]>dis[mid]+side[i].w){dis[side[i].to]=dis[mid]+side[i].w;if(flag){pd[side[i].to]=mid;ps[side[i].to]=i;}if(!iq[side[i].to]){iq[side[i].to]=1;qq.push(side[i].to);}}}flag=0;
}
int main()
{int ans;scanf("%d",&exp);while(exp--){init();spfa();if(dis[num_dot]>50000000)printf("-1\n");else{ans=0;for(int i=num_dot;i>1;i=pd[i]){die[ps[i]]=1;die[side[ps[i]].co]=1;spfa();ans=max(ans,dis[num_dot]);die[ps[i]]=0;die[side[ps[i]].co]=0;}if(ans>50000000)printf("-1\n");elseprintf("%d\n",ans);}}
}