P1171 售货员的难题

题目描述

某乡有nn个村庄(1<n \le 201<n≤20)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)s(0<s<1000)是已知的，且AA村到BB村与BB村到AA村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为11，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

即 \(1--> all --> 1\) 路径总长度最小

---

调试日志： 又把 \(1 << (i - 1)\) 写成了 \(1 << (num - 1)\)

小插曲： 卡空间卡到阿苏发稿地方OD撒龙卷风no， 然后这题常规做法只能开 \(O^{2}\) 过

---

Solution

经典状压dp

\(dp[i][j]\) 表示 \(i\) 状态下最后一个点走 \(j\) 的最短路径长度

转移见代码

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = (1 << 20);

int num;

int map[21][21], one[21];

int dp[maxn][21];

int main(){

	num = RD();

	REP(i, 1, num)REP(j, 1, num)map[i][j] = RD();

	int maxstate = (1 << num) - 1;

	memset(dp, 63, sizeof(dp));

	REP(i, 1, num)one[i] = (1 << (i - 1));

	dp[one[1]][1] = 0;

	REP(i, 0, maxstate){

		REP(j, 1, num){

			if(i & one[j]){

				REP(k, 1, num){

					if(i & one[k])continue;

					dp[i | one[k]][k] = min(dp[i | one[k]][k], dp[i][j] + map[j][k]);

					}

				}

			}

		}

	int ans = maxn;

	REP(i, 2, num)ans = min(ans, dp[maxstate][i] + map[i][1]);

	printf("%d\n", ans);

	return 0;

	}