hdu 1595 find the longest of the shortest（dijstra + 枚举）

2020-11-18 16:50

阅读：761

标签：最短路

http://acm.hdu.edu.cn/showproblem.php?pid=1595

大致题意：

给一个图，让输出从中删除任意一条边后所得最短路径中最长的。。

思路：

直接枚举每条边想必是不行的。其实有些边是不需要枚举的，因为删除它们并不影响起点到终点的最短路。起作用的边都是未删边前的最短路径上的边，删除它们最短距离肯定增大，只需在这些最短距离中求最大的即可。

记录最短路径上的边，只需一个pre数组记录松弛时每个点的前驱节点。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
using namespace std;

const int maxn = 1010;
const int INF = 0x3f3f3f3f;

int n,m;
int mapp[1010][1010];
int dis[maxn],vis[maxn];
int pre[maxn],pre1[maxn];
int ans;

void init()
{
    for(int i = 1; i  dis[j] && !vis[j])
            {
                min = dis[j];
                pos = j;
            }
        }

        vis[pos] = 1;
        for(int j = 1; j  dis[pos] + mapp[pos][j])
            {
                dis[j] = dis[pos] + mapp[pos][j];
                pre[j] = pos;
            }
        }
    }
    return dis[n];

}

void solve()
{
    memcpy(pre1,pre,sizeof(pre));
    ans = -1;

    int u = n;

    while(pre1[u] != -1)
    {
        int tmp = mapp[pre1[u]][u];
        
        mapp[pre1[u]][u] = mapp[u][pre1[u]] = INF; //删除该边
        
        int res = dijstra(1);
        if(res != INF)
            ans = max(ans,res);
            
        mapp[ pre1[u] ][u] = mapp[u][ pre1[u] ] = tmp;
        
        u = pre1[u];
    }
    printf("%d\n",ans);
}

int main()
{
    int u,v,w;
    while(~scanf("%d %d",&n,&m))
    {
        init();

        for(int i = 0; i 

hdu 1595 find the longest of the shortest（dijstra + 枚举）
标签：最短路
原文地址：http://blog.csdn.net/u013081425/article/details/24611089

上一篇：复制网页文字有背景，怎么办？

下一篇：php中奖概率算法，可用于刮刮卡，大转盘等抽奖算法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：hdu 1595 find the longest of the shortest（dijstra + 枚举）
文章链接：http://soscw.com/essay/21877.html

亲，登录后才可以留言！

hdu 1595 find the longest of the shortest（dijstra + 枚举）

评论

热门文章

推荐文章

最新文章

置顶文章