ACM-售货员难题

题目描述：售货员的难题

 某乡有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 = 100;
int n, ans, vis[MAX], map[MAX][MAX];

void DFS(int pos, int sum, int cnt)
{
    //cout << "pos:" << pos << "	sum:" << sum << "	cnt:" << cnt << endl;
    if (cnt == n)
    {
        //cout << "===========end============:" << "sum:" << sum << "	ans:" << ans << endl;
        sum += map[pos][0];
        ans = min(sum, ans);
        return;
    }
    if (sum > ans) return;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            if (sum + map[pos][i] > ans) continue;
            vis[i] = 1;
            DFS(i, sum + map[pos][i], cnt + 1);
            vis[i] = 0;
            
        }
    }

}

int main()
{
    memset(vis, 0, sizeof(vis));
    memset(map, 0, sizeof(map));
    ans = 0x3f3f3f3f;

    string str;
    cin >> n;
    getline(cin, str);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
        getline(cin, str);

    }
    
    vis[0] = 1;
    DFS(0, 0,1);

    cout << ans << endl;


    return 0;
}

预处理一下就好了。

#include<iostream>
#include<cstdio>
using namespace std;
int n, g[20][20], r[20][20], f[20], ans = 0x7fffffff;
void Dfs(int now, int sum, int dis)
{
    if (dis + r[now][1] >= ans)return; //如果最小距离仍然大于最优解，直接减枝
    if (dis>ans)return;
    if (sum == n)
    {
        ans = min(ans, dis + g[now][1]);
        return;
    }
    for (int i = 1; i <= n; i++)
    if (f[i] == 0)
    {
        f[i] = 1; Dfs(i, sum + 1, dis + g[now][i]); f[i] = 0;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        scanf("%d", &g[i][j]), r[i][j] = g[i][j];
    for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        r[i][j] = min(r[i][j], r[i][k] + r[j][k]); //计算两点之间的最小距离
    f[1] = 1;
    Dfs(1, 1, 0);
    printf("%d
", ans);
    return 0;
}