售货员的难题(codevs 2596)
2024-08-30 16:50:03
题目描述 Description
某乡有n个村庄(1<n<=15),有一个售货员,他要到各个村庄去售货,各村庄之间的路程s(0<s<1000)是已知的,且A村到B村与B村到A村的路大多不同。为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为1,他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入描述 Input Description
村庄数n和各村之间的路程(均是整数)
输出描述 Output Description
最短的路程
样例输入 Sample Input
3
0 2 1
1 0 2
2 1 0
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
本题可用最短路思想、搜索来解决,但是可能无法通过一组极限数据(且效率较低)。建议按树状DP考虑!
/*
不会什么树形DP,我做的是spfa(其实floyed就可以)+深搜+剪枝
首先将边反向,spfa处理所有点到1的距离,以备剪枝使用
然后深搜得到答案
剪枝:利用spfa得到的距离,当当前的dis+(n-t)*minn+f[x]>ans时,剪枝
(minn是矩阵中的最短距离,n-t是还有几步可以遍历完所有的村庄)
*/
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#define M 20
#define INF 3000000
using namespace std;
int map[M][M],f[M],n,ans=INF,min1=INF;
int a2[M][M];
bool vis[M];
queue<int> q;
int read()
{
char c=getchar();int num=,flag=;
while(c<''||c>''){if(c=='-')flag=-;c=getchar();}
while(c>=''&&c<=''){num=num*+c-'';c=getchar();}
return num*flag;
}
void dfs(int x,int t,int dis)
{
if(dis>ans)return;
if(dis+(n-t)*min1+f[x]>ans)return;
if(t==n)
{
ans=min(ans,dis+map[x][]);
return;
}
for(int i=;i<=n;i++)
if(!vis[i])
{
vis[i]=true;
dfs(i,t+,dis+map[x][i]);
vis[i]=false;
}
}
void spfa()
{
q.push();
vis[]=;
f[]=;
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=;
for(int i=;i<=n;i++)
if(a2[x][i]&&f[x]+a2[x][i]<f[i])
{
f[i]=f[x]+a2[x][i];
if(!vis[i])
{
vis[i]=;
q.push(i);
}
}
}
}
int main()
{
memset(f,0x3f3f3f3f,sizeof(f));
n=read();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
map[i][j]=read();
a2[j][i]=map[i][j];
min1=min(min1,map[i][j]);
}
spfa();
memset(vis,,sizeof(vis));
vis[]=;
dfs(,,);
printf("%d",ans);
return ;
}
最新文章
- ubuntu更新软件源
- The Swift Programming Language 中文翻译版(个人翻新随时跟新)
- JS-改变页面的颜色之变化核心-获取六位的随机数
- 2015.05.14:codesmith
- SimpleAdapter类使用方法
- POJ 2253 Difference of Clustering
- EBS基础—表的后缀
- 使用 CKEditor 上传图片, 粘贴屏幕截图
- 微信公众号问题:{";errcode";:40125,";errmsg";:";invalid appsecret, view more at http:\/\/t.cn\/LOEdzVq, hints: [ req_id: kL8J90219sg58 ]";}
- CSS 权威指南 CSS实战手册 第四版(阅读笔记)
- [Kubernetes] CRI 的设计与工作原理
- CPU的概念
- nexus-3.2.0-01.zip安装以及如何启动服务
- _itemmod_exchange_item
- Linux下文件的三种时间标记(atime ctime mtime)
- js实现点击按钮弹出上传文件的窗口
- 漂亮的ActionBar效果
- AVG
- nat转发
- redis 设置认证
热门文章
- mongodb多条件查询总结
- js Math 对象
- Linux目录结构及详细介绍
- python_对字符串操作.join() 效率 比 + 效率高
- iview table 勾选当前行代码 data key _checked: true
- docker的安装及基础操作与镜像构建
- 从postgres数据库逆向生成hibernate实体类
- mybatis中配置中引入properties文件
- HTML基础(二)列表标签
- 解决Invalid bound statement (not found)(Mybatis的Mapper绑定问题)