`

【记忆化搜索+最短路】HDU 2833 WuKong

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=2833

题意:求2条最短路径的最多公共点数
首先要说的是:求出最短路后,如果dist[u] + map[u][v] = dist[v],则uv这条边必定在最短路上


#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 305

int n, map[M][M], d1[M], d2[M], dp[M][M];
bool mark[M];

void init ()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            map[i][j] = inf;
    memset (dp, -1, sizeof(dp));
}

void dijk (int u, int dist[])
{
    memset (mark, false, sizeof(mark));
    int mins, i, j, v;
    for (i = 1; i <= n; i++)
        dist[i] = map[u][i];
    dist[u] = 0;
    mark[u] = true;
    while (1)
    {
        mins = inf;
        for (j = 1; j <= n; j++)
            if (!mark[j] && dist[j] < mins)
                mins = dist[j], v = j;
        if (mins == inf)
            break;
        mark[v] = true;
        for (j = 1; j <= n; j++)
            if (!mark[j] && dist[v] + map[v][j] < dist[j])
                dist[j] = dist[v] + map[v][j];
    }
}

int dfs (int a, int b)
{
    if (dp[a][b] > -1)		//记忆
        return dp[a][b];
    int i, j, v = 0;    //v是重要的临时值
    if (a == b)				//a==b可以一起往前走一步
    {
        v++;
        for (i = 1; i <= n; i++)		//枚举第一条最短路的可以到达a的前一个点
        {
            if (d1[i] + map[i][a] != d1[a])		//ia不是最短路上的边
                continue;
            for (j = 1; j <= n; j++)	//枚举第二条最短路的可以到达b的前一个点
                if (d2[j] + map[j][b] == d2[b])
                    v = max (v, dfs (i, j)+1);
        }
    }
    for (i = 1; i <= n; i++)		//a往前走一步
        if (d1[i] + map[i][a] == d1[a])
            v = max (v, dfs (i, b));
    for (i = 1; i <= n; i++)		//b往前走一步
        if (d2[i] + map[i][b] == d2[b])
            v = max (v, dfs (a, i));
    dp[a][b] = v;
    return v;
}

int main()
{
    int m, u, v, w, A, B, C, D;
    while (scanf ("%d%d", &n, &m), (n||m))
    {
        init ();
        while (m--)
        {
            scanf ("%d%d%d", &u, &v, &w);
            if (w < map[u][v])
                map[u][v] = map[v][u] = w;
        }
        scanf ("%d%d%d%d", &A, &B, &C, &D);
        dp[A][C] = 0;
        if (A == C)			//dfs重要返回条件
            dp[A][C] = 1;
        dijk (A, d1);
        dijk (C, d2);
        printf ("%d\n", dfs (B, D));	//dfs(A, C)会超时……要从终点走回起点
    }
    return 0;
}
1
1
分享到:
评论

相关推荐

    最短路(HDU-2544).rar

    《最短路问题详解》 在计算机科学领域,最短路问题是一个经典的图论问题,其目标是寻找网络中两点间路径的最小成本。这个问题在众多应用中都有所体现,如交通规划、通信网络设计、社交网络分析等。在本篇内容中,...

    hdu.rar_hdu

    2. **高级算法**:包括动态规划(状态转移、记忆化搜索)、贪心策略、回溯法、分支限界法等。 3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、...

    HDU最全ac代码

    5. **优化技巧**:如何减少时间复杂度,使用位运算优化、循环展开、记忆化搜索等方法提升代码效率。 6. **调试和测试**:理解如何编写测试用例来检查代码的正确性,以及如何利用调试工具定位和修复错误。 7. **...

    小数化分数2(hdu1717)

    题目"小数化分数2(hdu1717)"正是这样一种挑战,它要求我们开发一个算法来精确地表示给定的小数为一个分数形式。 首先,我们要理解小数到分数转换的基本原理。对于有限小数,这个过程相对直接,因为我们可以直接...

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    ACM HDU题目分类

    搜索题是 ACM HDU 题目分类中的一大类,例如,1010 搜索题,剪枝很关键;1016 经典的搜索;1026 搜索;1043 经典搜索题,八数码问题;1044 稍微有点麻烦的搜索题;1045 搜索题,可用匹配做 等等。 贪心算法 贪心...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    二叉搜索树练习 HDU3791

    2. **图形化工具**:如Graphviz,可视化二叉搜索树,帮助理解数据结构和算法的执行过程。 3. **编译器/解释器**:如JDK的javac或IDE,用于编译和运行Java程序。 4. **在线评测系统**:如HDU的OJ系统,提交代码并获取...

    hdu acm 教案(7)

    7. **记忆化搜索**:在动态规划或递归问题中,记忆化搜索是一种优化技术,它将已经计算过的结果存储起来,避免重复计算,从而提高效率。这种方法在解决复杂度较高的问题时非常有用,如斐波那契数列、最短路径问题等...

    HDU+2000-2099+解题报告

    HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    hdu acm 教案(3)

    5. **记忆化搜索**:这是动态规划的一种实现方式,通过使用数组或矩阵存储已解决的子问题结果,避免重复计算,提高效率。 6. **自底向上的动态规划**:与递归相反,这种方法从最小的子问题开始,逐步解决更大的问题...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

Global site tag (gtag.js) - Google Analytics