题目描述:售货员的难题 某乡有n个村庄(1< n < 20),有一个售货员,他要到各个村庄去售货,各村庄之间的路程s(0 < s < 1000)是已知的,且A村到B村与B村到A村的路大多不同。为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为 1,他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入
村庄数n和各村之间的路程(均是整数)。
输出
最短的路程
样例输入
3{村庄数}
0 2 1{村庄1到各村的路程}
1 0 2{村庄2到各村的路程}
2 1 0{村庄3到各村的路程}
样例输出
3思路:就是DFS,但是减枝比较麻烦,还可以用DP。这种写法超时!!!
// 售货员的难题.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;const int MAX = ;
int n, ans, vis[MAX], map[MAX][MAX];void DFS(int pos, int sum, int cnt)
{
//cout << "pos:" << pos << "\tsum:" << sum << "\tcnt:" << cnt << endl;
if (cnt == n)
{
//cout << "===========end============:" << "sum:" << sum << "\tans:" << ans << endl;
sum += map[pos][];
ans = min(sum, ans);
return;
}
if (sum > ans) return;
for (int i = ; i < n; i++)
{
if (!vis[i])
{
if (sum + map[pos][i] > ans) continue;
vis[i] = ;
DFS(i, sum + map[pos][i], cnt + );
vis[i] = ; }
}}int main()
{
memset(vis, , sizeof(vis));
memset(map, , sizeof(map));
ans = 0x3f3f3f3f; string str;
cin >> n;
getline(cin, str);
for (int i = ; i < n; i++)
{
for (int j = ; j < n; j++)
cin >> map[i][j];
getline(cin, str); } vis[] = ;
DFS(, ,); cout << ans << endl; return ;
}
预处理一下就好了。
#include<iostream>
#include<cstdio>
using namespace std;
int n, g[][], r[][], f[], ans = 0x7fffffff;
void Dfs(int now, int sum, int dis)
{
if (dis + r[now][] >= ans)return; //如果最小距离仍然大于最优解,直接减枝
if (dis>ans)return;
if (sum == n)
{
ans = min(ans, dis + g[now][]);
return;
}
for (int i = ; i <= n; i++)
if (f[i] == )
{
f[i] = ; Dfs(i, sum + , dis + g[now][i]); f[i] = ;
}
}
int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
scanf("%d", &g[i][j]), r[i][j] = g[i][j];
for (int k = ; k <= n; k++)
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
r[i][j] = min(r[i][j], r[i][k] + r[j][k]); //计算两点之间的最小距离
f[] = ;
Dfs(, , );
printf("%d\n", ans);
return ;
}