HDU - 3001 Travelling 状压dp + 三进制 [kuangbin带你飞]专题二
2024-10-20 03:23:02
终于刷完搜索专题了。
题意:给定n个城市,每个城市参观不能超过两次,两个城市之间有道路通过需要花费X,求通过能所有城市的最小花费。
思路:每个城市有三个状态0,1,2,可用三进制存储所有城市的访问状态。DP[i][j]表示当前状态为i,j是道路的最后一个城市。
如果j城市可以到达k城市,那么下一个状态就是next = i + bit[k],转移方程DP[next][k] = min(DP[next][k], DP[i][j] + cost[j][k]),cost[j][k]表示城市j到k的花费。
AC代码: 374ms
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<utility> using namespace std; typedef pair<int, int> PI; const int inf = 0x3f3f3f3f; const int maxn = 60000; int num[maxn][15], bit[15], cost[15][15], dp[maxn][15]; void init() { bit[0] = 1; for(int i = 1; i <= 10; ++i) bit[i] = bit[i - 1] * 3; for(int i = 0; i < bit[10]; ++i) { int x = i; for(int j = 0; j < 10; ++j) { num[i][j] = x % 3; x /= 3; } } } int main() { init(); int n, m; while(scanf("%d%d", &n, &m) == 2) { memset(cost, -1, sizeof(cost)); int x, y, c; for(int i = 0; i < m; ++i) { scanf("%d%d%d", &x, &y, &c); if(cost[x-1][y-1] == -1) { cost[x-1][y-1] = cost[y-1][x-1] = c; } else { cost[x-1][y-1] = cost[y-1][x-1] = min(cost[x-1][y-1], c); //去重边 } } memset(dp, inf, sizeof(dp)); //初始化边界 for(int i = 0; i < n; ++i) { dp[ bit[i] ][i] = 0; } int ans = inf; for(int i = 0; i < bit[n]; ++i) { int flag = 1; for(int j = 0; j < n; ++j) { if(num[i][j] == 0) flag = 0; //当前状态有从未经过的点 if(dp[i][j] == inf) continue; for(int k = 0; k < n; ++k) { if(k == j || num[i][k] >= 2 || cost[j][k] == -1) continue; int walk = i + bit[k]; //转换到新的状态 dp[walk][k] = min(dp[walk][k], dp[i][j] + cost[j][k]); } } if(flag) { for(int j = 0; j < n; ++j) ans = min(ans, dp[i][j]); } } if(ans == inf) ans = -1; printf("%d\n", ans); } return 0; }
如有不当之处欢迎指出!
最新文章
- 小丁带你走进git的世界四-重写历史记录
- Javascript学习笔记:9种创建对象的方式
- sourceinsight技巧
- Winform开发框架之权限管理系统的改进
- 记一次查内存异常问题(续《记一次Web应用CPU偏高》)
- Linux下升级python
- 伪静态(URL重写)
- java 数据库编程 学习笔记 不断更新
- MySQL的小Tips
- maven工程,java代码加载resources下面资源文件的路径
- Linux内核设计与实现 第十七章
- 《Java并发编程实战》笔记-Happens-Before规则
- How to return AJAX errors from Laravel Controller?
- UVA 227 Puzzle(基础字符串处理)
- JavaScript进阶系列01,函数的声明,函数参数,函数闭包
- [AWS vs Azure] 云计算里AWS和Azure的探究(2.1)
- testNG 学习笔记 Day 3 常用的断言
- 首页设计的可用性和PET
- python-Event事件处理进程同步
- C#-创建并添加TXT文件