hdu 1599 find the mincost route 无向图的最小环 求从一个点遍历所有节点以后回到原点的最短

本文主要是介绍hdu 1599 find the mincost route 无向图的最小环 求从一个点遍历所有节点以后回到原点的最短,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

在写题解之前给自己打一下广告哈~委屈。。抱歉了,希望大家多多支持我在CSDN的视频课程,地址如下:

http://edu.csdn.net/course/detail/209


题目:

find the mincost route

Time Limit: 1000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2801    Accepted Submission(s): 1115


Problem Description
杭州有N个景区,景区之间有一些双向的路来连接,现在8600想找一条旅游路线,这个路线从A点出发并且最后回到A点,假设经过的路线为V1,V2,....VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区,而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线,并且花费越少越好。

Input
第一行是2个整数N和M(N <= 100, M <= 1000),代表景区的个数和道路的条数。
接下来的M行里,每行包括3个整数a,b,c.代表a和b之间有一条通路,并且需要花费c元(c <= 100)。

Output
对于每个测试实例,如果能找到这样一条路线的话,输出花费的最小值。如果找不到的话,输出"It's impossible.".

Sample Input
 
3 31 2 12 3 11 3 13 31 2 11 2 32 3 1

Sample Output
 
3It's impossible.

Author
8600

Source
HDU 2007-Spring Programming Contest - Warm Up (1)

Recommend


题目分析:

                无向图的最小环。

Floyd 算法保证了最外层循环到 k 时所有顶点间已求得以 0…k-1 为中间点的最短路径。一个环至少有3个顶点,设某环编号最大的顶点为 L ,在环中直接与之相连的两个顶点编号分别为 M 和 N (M,N < L),则最大编号为 L 的最小环长度即为 Graph(M,L) + Graph(N,L) + Dist(M,N) ,其中 Dist(M,N) 表示以 0…L-1 号顶点为中间点时的最短路径,刚好符合 Floyd 算法最外层循环到 k=L 时的情况,则此时对 M 和 N 循环所有编号小于 L 的顶点组合即可找到最大编号为 L 的最小环。再经过最外层 k 的循环,即可找到整个图的最小环。、


需要注意的是,当报Runtime Error (ACCESS_VIOLATION)错误的时候有可能是因为数据读取出现了问题。把根据边数读取写成了根据点数读取。


代码如下:

/* * d.cpp * *  Created on: 2015年2月7日 *      Author: Administrator */#include <iostream>#include <cstdio>#include <cmath>using namespace std;const int maxn = 110;const int inf = 1000000;int dist[maxn][maxn];int e[maxn][maxn];int n,m;void initial()int i; int j; for(i = 1 ; i <= n ; ++i){  for(j = 1 ; j <= n ; ++j){   if(i == j){    e[i][j] = 0;   }else{    e[i][j] = inf;   }  } }}int floyd()int i; int j; int k; int mincircle = inf;// dist = e; for(i = 1 ; i <= n ; ++i){  for(j = 1 ; j <= n ; ++j){   dist[i][j] = e[i][j];  } } //根据Floyed的原理,在最外层循环做了k-1次之后,dis[i][j]则代表了i到j的路径中所有结点编号都小于k的最短路径 for(k = 1 ; k <= n ; ++k){  //环的最小长度为edge[i][k]+edge[k][j]+i->j的路径中所有编号小于k的最短路径长度  for(i = 1 ; i < k ; ++i){   for(j = i+1 ; j < k ; ++j){    if(dist[i][j] + e[i][k] + e[k][j] < inf){     mincircle = min(mincircle,dist[i][j] + e[j][k] + e[k][i]);    }   }  }   //floyd原来的部分,更新dist[i][j]  for(i = 1 ; i <= n ; ++i){   for(j = 1 ; j <= n ; ++j){    if(dist[i][j] > dist[i][k] + dist[k][j]){     dist[i][j] = dist[i][k] + dist[k][j];    }   }  } } return mincircle;}int main()while(scanf("%d%d",&n,&m)!=EOF){  initial();  int i;  for(i = 1 ; i <= m ; ++i){   int a;   int b;   int c;   scanf("%d%d%d",&a,&b,&c);   if(e[a][b] > c){    e[a][b] = e[b][a] = c;   }  }  int ans = floyd();  if(ans != inf){   printf("%d\n",ans);  }else{   printf("It's impossible.\n");  } } return 0;}





           

给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow
这里写图片描述

这篇关于hdu 1599 find the mincost route 无向图的最小环 求从一个点遍历所有节点以后回到原点的最短的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/306862

相关文章

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c