首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

[hdu2544]最短路

作者：陈汉文爱_290 | 来源：互联网 | 2023-10-11 16:10
简单的最短路径题题目页：http:acm.hdu.edu.cnshowproblem.php?pid2544没什么好说的，可以用单源最短路径的各种算法解题，所有节点对的最短路径……

简单的最短路径题

题目页：http://acm.hdu.edu.cn/showproblem.php?pid=2544

没什么好说的，可以用单源最短路径的各种算法解题，所有节点对的最短路径…………解题，这里用 dijkstra 算法。练习一下 dijkstra 算法。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include 
 
#define Infinite  10000000
int  number_points, number_ways;
int  buffer_consume[110][110];
int  dist[110];
bool discovered[110];
 
// return: 返回未发现顶点的最短路径的下标
// remark: 遍历搜寻未发现顶点的最短路径的下标，
//         预计耗时 O(v)
int getMinIndex()
{
    int min_value = Infinite;
    int min_index = 0;
    for (int i = 1; i <= number_points; i++)
    {
        if (discovered[i] == false && dist[i] <= min_value)
        {
            min_value = dist[i];
            min_index = i;
        }
    }
 
    return min_index;
};
 
void dijkstra()
{
    for (int i = 1; i <= number_points; i++)
    {
        dist[i] = buffer_consume[1][i];
        discovered[i] = false;
    }
 
    dist[1] = 0;
    discovered[1] = true;
 
    for (int count = 1; count != number_points; count++)
    {
        int u = getMinIndex(); // 获取未发现顶点的最短路径的下标
        discovered[u] = true;  // 标记为已发现
 
        if (u == number_points) // 目标顶点已被发现，算法终止。
            return;
 
        // for each (u, v) 松弛操作
        for (int v = 1; v <= number_points; v++)
        {
            if (dist[u] + buffer_consume[u][v] < dist[v])
                dist[v] = dist[u] + buffer_consume[u][v];
        }
    }
}
 
int main()
{
    // 读取第一组数据的两行
    scanf("%d%d", &number_points, &number_ways);
 
    while(number_points != 0 && number_ways != 0)
    {
        // 1. 初始化
        for (int x = 1; x <= number_points; x++)
        for (int y = 1; y <= number_points; y++)
        {
            buffer_consume[x][y] = Infinite;
        }
 
        // 2. 读取路径
        for (int i = 0; i < number_ways; i++)
        {
            int x, y, consume;
            scanf("%d%d%d", &x, &y, &consume);
            buffer_consume[x][y] = consume;
            buffer_consume[y][x] = consume;
        }
 
        // 3. dijkstra 算法
        dijkstra();
 
        // 4. 输出答案
        printf("%d\n", dist[number_points]);
 
        // 5. 读取下一组数据
        scanf("%d%d", &number_points, &number_ways);
    }
 
    return 0;
}

[hdu 2544] 最短路
推荐阅读
  • int

    HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

    HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • 数组

    动态规划算法的基本步骤及最长递增子序列问题详解

    动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]
  • case

    求解hdu 1003 java题目的动态规划优化方法

    本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]
  • int

    《数据结构》学习笔记3——串匹配算法性能评估

    《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
  • int

    指针的引用以及在什么情况下使用指针的引用

    本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址，通过指针可以修改指针所指的变量的值。然而，如果想要修改指针的指向，就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法，并思考了在修改指针的指向后，取指针的输出结果。 ... [详细]
  • int

    lua语言闭包、模式匹配、日期、编译、模块的特性及应用

    本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]
  • 数组

    Java实现大数乘法（分治算法）

    本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • merge

    C#之数据集：DataSet对象的使用及相关方法详解

    本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]
  • copy

    OC学习笔记之@property和@synthesize

    本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]
  • int

    Linux进程控制块PCBtask_struct结构体结构及作用详解

    本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]
  • 数组

    java 线程死锁模拟

    1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]
  • default

    高质量SQL书写的30条建议

    高质量SQL书写的30条建议
    本文提供了30条关于优化SQL的建议，包括避免使用select *，使用具体字段，以及使用limit 1等。这些建议是基于实际开发经验总结出来的，旨在帮助读者优化SQL查询。 ... [详细]
  • default

    asp.net微信公众平台开发目录汇总陆续更新的相关内容

    本文内容为asp.net微信公众平台开发的目录汇总，包括数据库设计、多层架构框架搭建和入口实现、微信消息封装及反射赋值、关注事件、用户记录、回复文本消息、图文消息、服务搭建（接入）、自定义菜单等。同时提供了示例代码和相关的后台管理功能。内容涵盖了多个方面，适合综合运用。 ... [详细]
  • int

    C#生成随机数的三种方法及其问题分析

    本文介绍了C#中生成随机数的三种方法，并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法，但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数，进一步突显了这个问题。文章指出，随机数生成在任何编程语言中都是必备的功能，但Random类生成的随机数并不可靠。最后，提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]
  • int

    VB.NET在线急等问题解决方法，如何统计数据库字段下的数据并显示在文本框里？

    本文介绍了一个在线急等问题解决方法，即如何统计数据库中某个字段下的所有数据，并将结果显示在文本框里。作者提到了自己是一个菜鸟，希望能够得到帮助。作者使用的是ACCESS数据库，并且给出了一个例子，希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句，得到的结果是650，但不知道如何得到560。希望能够得到解决方案。 ... [详细]
author-avatar
陈汉文爱_290
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有