最短路（bellman）-hdu1217-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

最短路（bellman）-hdu1217

阅读量：5377 次

发布时间：2019-06-15

本文共 1611 字，大约阅读时间需要 5 分钟。

Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。

这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。

由于此题中需要求的是有一种货币A，通过一系列的转化，能够再次转化回A，因此，运用bellman算法来解决此题。

具体的关于bellman最短路的求法请见转载博客：

题目链接：

题目描述：

代码描述：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          using namespace std;const int MAX_E  = 1000;const int MAX_V = 33;const int INF = 0x3f3f3f3f;struct node{    int from,to;    double cost;}es[MAX_E*4];//用于存图int cae=0;int V,E;double d[MAX_V];map
          
            mp;//将字符串问题转换为数字问题bool bellman(int s){ //fill(d,d+MAX_V,-2); for(int i=0;i
           
            > V && V){ mp.clear(); for(int i=0;i
            
             > str; mp[str]=i;//将str的“下标”赋值为i，即为了方便后续存图，用数字i来代替字符串str } cin >> E; map
             
              ::iterator it;//迭代器用于遍历map中的元素 for(int i=0;i
              
               > str1 >> cost >> str2; it=mp.find(str1);//查找函数，即找到str1在mp中的位置 es[i].from=it->second;//将找到的str1对应的“下标”，将结点i的起点值赋值为str1所对应的下标值 it=mp.find(str2); es[i].to=it->second;//将找到的str2对应的“下标”，将结点i的终点值赋值为str1所对应的下标值 es[i].cost=cost;//把结点i由起点from->to所对应的边的边长赋值为cost } solve(); } return 0;}

转载于:https://www.cnblogs.com/LJHAHA/p/10013745.html

你可能感兴趣的文章

ubuntu更改源为aliyun的源;ROS改为新加坡源

正则表达式入门

Halcon标定与自标定

Non-local Neural Networks

apache Internal Server Error 解决方法

Ubuntu14.04安装CUDA8.0与Cudnn5.1

（七）STM32的RTC简单操作

Floyd最短路算法

【转】Java并发编程：并发容器之ConcurrentHashMap

thinkphp5.0独立配置

day2逻辑运算作业详解

JQuery将DataTable list<>数据转换成JSON数据动态创建表格显示数据

MySQL中的information_schema

一般路由设置

JS 无法清除Cookie的解决方法

OCP 042、043、047最新题库+考试模拟器免费共享

P3708 koishi的数学题

大量视频资料

获取客户端ip、地理信息、浏览器、真实IP的php类库

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-12-01 00:35:48 当前IP: 3.142.98.60 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我