hdu 1599 find the mincost route 最小环
2024-08-27 11:42:59
题目链接:HDU - 1599
杭州有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)。
接下来的M行里,每行包括3个整数a,b,c.代表a和b之间有一条通路,并且需要花费c元(c <=
100)。
Output
对于每个测试实例,如果能找到这样一条路线的话,输出花费的最小值。如果找不到的话,输出"It's
impossible.".
impossible.".
题意描述:中文题,如上所述。
算法分析:用Floyd求解最小环的问题。有关最小环的定义和求解方法,大家可以去这个博客学习。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int maxn=+; int n,m;
int dist[maxn][maxn],edge[maxn][maxn]; void floyd()
{
int ans=;
for (int i= ;i<=n ;i++)
{
for (int j= ;j<=n ;j++)
dist[i][j]=edge[i][j];
}
for (int k= ;k<=n ;k++)
{
for (int i= ;i<k ;i++)
{
for (int j=i+ ;j<k ;j++)
{
if (dist[j][i]+edge[i][k]+edge[k][j]<)
ans=min(ans,dist[j][i]+edge[i][k]+edge[k][j]);
}
}
for (int i= ;i<=n ;i++)
{
for (int j= ;j<=n ;j++)
{
if (dist[i][j]>dist[i][k]+dist[k][j])
dist[i][j]=dist[i][k]+dist[k][j];
}
}
}
if (ans==) printf("It's impossible.\n");
else printf("%d\n",ans);
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
for (int i= ;i<=n ;i++)
{
for (int j= ;j<=n ;j++)
edge[i][j]=;
edge[i][i]=;
}
int x,y,cost;
for (int i= ;i<m ;i++)
{
scanf("%d%d%d",&x,&y,&cost);
if (edge[x][y]>cost) edge[x][y]=edge[y][x]=cost;
}
floyd();
}
return ;
}
最新文章
- PHP的final关键字、static关键字、const关键字
- oracle initialization or shutdown in progress问题解决步骤
- winform下自绘提示框风格窗体
- Leetcode 66 Plus One STL
- js方法和prototype
- js的选择星级评分插件
- WPF AutoGeneratingColumn 绑定下拉框
- 数据导出到Excel中
- Django中的Model(表结构)
- 重定位表 IMAGE_BASE_RELOCATION
- [C++]引用浅析
- 让我的分页类获取sessionFactory
- 校园网IPv6加速
- WAMP中的MySQL设置用户、密码 及 phpmyadmin的配置
- python:PATH、PYTHONPATH 和 sys.path 的区别
- 福州大学软件工程1916|W班 第2次作业成绩排名
- 7-10 多项式A除以B (25 分)
- 用python 替换文件中的git地址
- [CodeForces - 447B] B - DZY Loves Strings
- vertical-align属性测试实验面板 文字 图片对齐
热门文章
- Spider_Man_6 の Scrapy_Downloader Middleware(针对一下&#128055;&#128055;&#128055;)
- rownum浅谈(二)
- C# 枚举相关操作——解析,遍历
- HDU 2491
- easyui中的依赖关系
- Codeforces Round #392(div 2) 758D (贪心)
- 在Linux上录制终端的操作
- 枪战(maf)
- 【CF Round 439 A. The Artful Expedient】
- AE中实现Control中的各种图形工具的方法