HDU-1595&3986-枚举+最短路

忘是亡心i 2022-07-11 12:11 82阅读 0赞

# find the longest of the shortest #

**Time Limit: 1000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 3120    Accepted Submission(s): 1148**

Problem Description

Marica is very angry with Mirko because he found a new girlfriend and she seeks revenge.Since she doesn't live in the same city, she started preparing for the long journey.We know for every road how many minutes it takes to come from one city to another.  
Mirko overheard in the car that one of the roads is under repairs, and that it is blocked, but didn't konw exactly which road. It is possible to come from Marica's city to Mirko's no matter which road is closed.  
Marica will travel only by non-blocked roads, and she will travel by shortest route. Mirko wants to know how long will it take for her to get to his city in the worst case, so that he could make sure that his girlfriend is out of town for long enough.Write a program that helps Mirko in finding out what is the longest time in minutes it could take for Marica to come by shortest route by non-blocked roads to his city.

Input

Each case there are two numbers in the first row, N and M, separated by a single space, the number of towns,and the number of roads between the towns. 1 ≤ N ≤ 1000, 1 ≤ M ≤ N\*(N-1)/2. The cities are markedwith numbers from 1 to N, Mirko is located in city 1, and Marica in city N.  
In the next M lines are three numbers A, B and V, separated by commas. 1 ≤ A,B ≤ N, 1 ≤ V ≤ 1000.Those numbers mean that there is a two-way road between cities A and B, and that it is crossable in V minutes.

Output

In the first line of the output file write the maximum time in minutes, it could take Marica to come to Mirko.

Sample Input

5 6
    1 2 4
    1 3 3
    2 3 1
    2 4 4
    2 5 7
    4 5 1
    
    6 7
    1 2 1
    2 3 4
    3 4 4
    4 6 4
    1 5 5
    2 5 2
    5 6 5
    
    5 7
    1 2 8
    1 4 10
    2 3 9
    2 4 10
    2 5 1
    3 4 7
    3 5 10

Sample Output

11
    13
    27

题目为1595，3986题目意思一样

题目大意：

给你一张双向图，现在有一条边是坏的，但是不知道是那一条，求出最坏的情况下的从1到n的最短路，也就是最短路中最长的那个

题目思路：

首先想到的肯定是枚举边，删除一条边跑一边最短路，然后取个最大的，当然思路也就是这样，但是不需要枚举所有的边，首先跑一边最短路可以得到

删除不在最短路上的边删除后答案都是一样的，所以我们只需删除最短路上的边，先跑一遍最短路，记录下边，，然后再去枚举这些边！

hdu1595：输入的数据保证都有解，并且不存在重边，不用考虑删除边后会出现不存在最短路的情况，所以dij和spfa都可以

AC代码：

#include<algorithm>
    #include<iostream>
    #include<cstdio>
    
    using namespace std;
    const int maxn = 1005;
    const int inf = 1e9;
    int dis[maxn],mp[maxn][maxn],vis[maxn],pre[maxn];
    int n,m;
    
    int dij(int flag){
       for(int i=2;i<=n;i++)vis[i]=0,dis[i]=inf;
       dis[1]=0,vis[1]=1;
       for(int i=1;i<=n;i++){
          int to = 1,v = inf;
          for(int j=2;j<=n;j++){
            if(!vis[j]&&v>dis[j])v=dis[j],to=j;
          }
          vis[to]=1;
          for(int j=2;j<=n;j++){
            if(!vis[j]&&dis[j]>dis[to]+mp[to][j]){
                dis[j]=dis[to]+mp[to][j];
                if(flag)pre[j]=to;
            }
          }
       }
       if(dis[n]==inf)return -1;
       else
       return dis[n];
    }
    
    int main()
    {
        while(cin>>n>>m){
            for(int i=1;i<=n;i++){
               pre[i]=i;
               for(int j=1;j<=n;j++)
                    if(i!=j)mp[i][j]=inf;
                    else mp[i][j]=0;
            }
            for(int i=0;i<m;i++){
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                mp[u][v]=mp[v][u]=w;
            }
            int Max=dij(1);
            int v = n;
            while(v!=1){
                int u = pre[v];
                int xx = mp[u][v];
                mp[u][v]=mp[v][u]=inf;
                Max = max(Max,dij(0));
                mp[u][v]=mp[v][u]=xx;
                v = pre[v];
            }
            printf("%d\n",Max);
        }
    
        return 0;
    }

hdu3986：要考虑不存在最短的情况，那样就输出-1，并且还有重边，所以只能用spfa

AC代码：

#include<algorithm>
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    
    using namespace std;
    const int maxn = 1005;
    const int inf = 1e9;
    int dis[maxn],vis[maxn],pre[maxn],hed[maxn],mp[maxn][maxn];
    int n,m,e,U,V,W;
    
    struct nod{
       int v,w,nex;
    }edge[maxn*maxn*2];
    
    void add(int u,int v,int w){
        edge[e].v = v,edge[e].w = w,edge[e].nex=hed[u],hed[u]=e++;
    }
    
    int spfa(int flag){
       for(int i=2;i<=n;i++)vis[i]=0,dis[i]=inf;
       dis[1]=0,vis[1]=1;
       int flag1=1;
       queue<int>q;
       q.push(1);
       while(!q.empty()){
        int u = q.front();q.pop();
        vis[u]=0;
        for(int i=hed[u];~i;i=edge[i].nex){
            int v = edge[i].v;
            if((u==U&&v==V||u==V&&v==U)&&i==W)continue;  //标记的删除的边
            if(dis[v]>dis[u]+edge[i].w){
                dis[v]=dis[u]+edge[i].w;
                if(flag)mp[u][v]=i,pre[v]=u;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
       }
       if(dis[n]==inf)return -1;
       else return dis[n];
    }
    
    int main()
    {
        int t;cin>>t;
        while(t--){
            scanf("%d%d",&n,&m);
            memset(hed,-1,sizeof(hed));
            e=1;
            for(int i=0;i<m;i++){
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                add(u,v,w);
                add(v,u,w);
            }
            U=-1,V=-1,W=-1;    //用来记录标记的边删除的边 u,v是点，w是该边的节点号（邻接表）
            int Max=spfa(1);
            int v = n;
            if(Max!=-1)
            while(v!=1){
                int u = pre[v];
                U=u,V=v,W=mp[u][v];
                int yy = spfa(0);
                if(yy==-1){Max=-1;break;}
                Max = max(Max,yy);
                v = pre[v];
            }
            printf("%d\n",Max);
        }
    
        return 0;
    }