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

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

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

我的做法是：

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

再一条一条边的删，

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

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

以此类推。

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

假设是无穷大则代表最坏情况为不通，按题意输出-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");

            else

                printf("%d\n",ans);

        }

    }

}