/*
http://oj.daimayuan.top/course/5/problem/249
蜗蜗的世界里有 n
个城市,城市两两之间通过高速公路连接,从第 i
个城市走到第 j
个城市需要花费 ai,j
的时间。
现在蜗蜗想从 1 号城市出发旅游,他想把每个城市都玩个遍,但又不想在一个城市玩两遍,玩完以后蜗蜗需要回到 1 号城市应付期末考试。请问蜗蜗最少需要花费多少时间?
蜗蜗到了一个城市以后,一定会在这个城市游玩。蜗蜗在出发之前会先在 1 号城市游玩。连接两个城市的高速公路不会经过其他城市。由于路况的原因,从第 i
个城市走到第 j
个城市花费的时间不一定等于从第 j
个城市走到第 i
个城市花费的时间。
输入格式
第一行一个整数 n
表示城市数目。
接下来 n
行,每行 n
个整数。第 i
行第 j
列的整数表示 ai,j
。
输出格式
一行一个整数表示答案。
样例输入
2
0 1
2 0
样例输出
3
数据范围
对于 100%
的数据,保证 2≤n≤18
,如果 i=j
,则 ai,j=0
,否则 1≤ai,j≤10000。
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20;
int dp[N][1 << N];
int n;
int mm[N][N];
bool isIn(int st, int a) {
if (st & (1 << a)) return true;
return false;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> mm[i][j];
}
}
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i < n; i++) {
dp[i][1 << i] = mm[0][i];
}
int ans = 0x3f3f3f3f;
for (int st = 0; st < (1 << n); st++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ( !isIn(st, j) && isIn(st, i)) {
dp[j][st | (1 << j)] = min(dp[j][st | (1 << j)], dp[i][st] + mm[i][j]);
}
if (j == 0 && (st | (1 << j)) == (1 << n) - 1) {
ans = min(ans, dp[j][st | (1 << j)]);
}
}
}
}
cout << ans << endl;
return 0;
}
标签:旅行,ai,城市,蜗蜗,int,include,249,dp
From: https://www.cnblogs.com/itdef/p/18530185