hdu 3001(三进制状压)
2024-08-27 22:17:53
题目
解法
看到这道题,我们就会想到旅行商问题。但是这里每一个点可以经过最多两次,所以我们用三进制表示就好了。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <vector>
#define INF 2139062143
#define MAX 0x7ffffffffffffff
#define del(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T&x)
{
x=;T k=;char c=getchar();
while(!isdigit(c)){if(c=='-')k=-;c=getchar();}
while(isdigit(c)){x=x*+c-'';c=getchar();}x*=k;
}
const int maxn=;
int dis[maxn][maxn];
int dp[][maxn];
int poww[]; void _init() {
poww[]=;
for(int i=;i<=;i++) poww[i]=poww[i-]*;
return;
} int query(int s,int k) {
return s/poww[k]%;
} int add(int x,int k) {
return x+poww[k];
} int n,m; bool check(int x) {
for(int i=;i<n;i++) if(!query(x,i)) return ;
return ;
} int main()
{
_init();
while(~scanf("%d %d",&n,&m)) {
del(dis,);del(dp,);
for(int i=,u,v,w;i<=m;i++) {
read(u),read(v),read(w);--u,--v;
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
} for(int i=;i<n;i++) dp[add(,i)][i]=; int ans=INF;
for(int s=;s<poww[n];s++) {
for(int i=;i<n;i++) {
if(!query(s,i)) continue;
for(int j=;j<n;j++) {
if(j==i||query(s,j)==||dis[i][j]==INF) continue;
dp[add(s,j)][j]=min(dp[s][i]+dis[i][j],dp[add(s,j)][j]);
}
if(check(s)) ans=min(ans,dp[s][i]);
}
}
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
return ;
}
最新文章
- jQuery的加法运算.
- 基本概率分布Basic Concept of Probability Distributions 8: Normal Distribution
- JavaScript:JavaScript事件的处理
- 数据库mysql中distinct关键词
- android项目中如何加载已有so库 <;转>;
- Win10无法上网提示缺少一个或者多个网络协议的处理方法
- spring中配置jndi数据源
- 设计模式-结合Android代码
- P44、面试题4:替换空格
- toastr
- 转载-smarty教程(基本语法)
- 浙大pat1019题解
- python中使用selenium调用Firefox缺少geckodriver解决方法
- Android APP 性能优化的一些思考
- iOS调用系统发送短信和邮件分享
- php final
- Apollo 代码的编译演示
- nginx配置优化 第二章
- Ubuntu16.04 python2.7升级python3.5
- 解决Ubuntu14.04安装Chrome浏览器打不开的问题
热门文章
- 虚拟化(四):vsphere高可用功能前提-共享存储搭建
- MySql解压版使用
- 【oracle 11G Grid 】Crsctl start cluster 和 crsctl start crs 有差别么?
- QT 4.53 for VS2005 编译包
- 【c语言】字符串替换空格:请实现一个函数,把字符串中的每一个空格替换成“%20”
- Linux gadget驱动分析1------驱动加载过程
- lucene 范围过滤
- Enter the path to the kernel header files for the 3.18.0-kali1-686-pae kerne vmware tool
- js基本功能大全
- X - Vasya and Socks