HDU 1595 find the longest of the shortest

在最短的时间最长。

含义非常模糊标题，做4小时度过理解问题……对中国不会死！

！。

它说，从 N 至 1 可能有一些办法的道路被封锁，不能。乞讨N 至 1 在最短的时间最长。

一般想法就是枚举每条路不能通过时候的最短路。时间花费太高。

m*O（SPFA）。

能够先做一次SPFA。把最短路径记录下来。

其它的路无论是不是封堵了，最短路都是这么多。

然后再枚举，把最短路径上的路依次删掉，求最短。

最多 (n-1)*O(SPFA);

最后输出最长的。

（我的代码太长，事实上能够把两个SPFA写在一起，推断一下就好，算了，关电脑睡觉。累！

）

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
struct lx
{
    int v,len;
};
vector<lx>g[1001];
int n,m,ans;
int path[1001];
struct edge
{
    int u,v;
};
stack<edge>flag;
void spfa()
{
    queue<int>q;
    bool vis[1001];
    int dis[1001];
    for(int i=1;i<=n;i++)
        dis[i]=INF,vis[i]=0;
    q.push(n);
    dis[n]=0,vis[n]=1;

    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int j=0;j<g[u].size();j++)
        {
            int v=g[u][j].v;
            int len=g[u][j].len;
            if(dis[v]>dis[u]+len)
            {
                dis[v]=dis[u]+len;
                path[v]=u;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    ans=dis[1];
    int tmp=1;
    while(tmp!=0)
    {
        edge now;
        now.v=tmp;
        tmp=path[tmp];
        now.u=tmp;
        if(tmp!=0)
        flag.push(now);
    }
}
void SPFA(edge now)
{
    queue<int>q;
    bool vis[1001];
    int dis[1001];
    for(int i=1;i<=n;i++)
        dis[i]=INF,vis[i]=0;
    q.push(n);
    dis[n]=0,vis[n]=1;

    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int j=0;j<g[u].size();j++)
        {
            int v=g[u][j].v;
            int len=g[u][j].len;
            if(u==now.u&&v==now.v)continue;
            if(dis[v]>dis[u]+len)
            {
                dis[v]=dis[u]+len;
                path[v]=u;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[1]!=INF)
        ans=max(ans,dis[1]);
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int u,v,len;
        for(int i=1;i<=n;i++)
            g[i].clear();
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&len);
            lx now;
            now.len=len;
            now.v=v,g[u].push_back(now);
            now.v=u,g[v].push_back(now);
        }
        while(!flag.empty())flag.pop();
        spfa();
        while(!flag.empty())
        {
            edge now=flag.top();flag.pop();
            //printf("%d -> %d
",now.u,now.v);
            SPFA(now);
        }
        printf("%d
",ans);
    }
}