网站开发完成如何上线,适合seo优化的网站制作,上海南桥网站建设,dede 网站入侵描述 给定一张 n 个点的带权无向图#xff0c;点从 0~n-1 标号#xff0c;求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数n。
接下来n行每行n个整数#xff0c;其中第i行第j个整数表示…描述 给定一张 n 个点的带权无向图点从 0~n-1 标号求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数n。
接下来n行每行n个整数其中第i行第j个整数表示点i到j的距离记为a[i,j]。
对于任意的x,y,z数据保证 a[x,x]0a[x,y]a[y,x] 并且 a[x,y]a[y,z]a[x,z]。
输出格式 输出一个整数表示最短Hamilton路径的长度。
数据范围 1≤n≤20 0≤a[i,j]≤107 输入样例 5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0 输出样例 18 一看到这道题目的时后我们一眼就觉得这是一道搜索题但是我们仔细分析一下时间复杂度 头尾都是确定的因此我们要对中间的n - 2个数进行全排列大概就是n - 2次方次排列于是我们自然而然的就想到了用DP来绝决这个问题但是用DP我们又该怎么样来表示这之间的状态呢。 每一个位置我们用01来表示。0代表没走过1代表已近走过 由此我们就有了状态转移方程。 DP[A][j] min(DP[A][j], DP[B][k] value[k][j]) 其中A、B分别时两个集合。B集合加上点 j 等于A集合。 每个状态用其第几位的二进制是0或者1来表示 我们有了下面的代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int maxn (1 20) 10;
int dp[maxn][22], value[22][22], n;
int main() {cin n;for(int i 0; i n; i)for(int j 0; j n; j)cin value[i][j];memset(dp, 0x3f, sizeof dp);dp[1][0] 0;for(int i 0; i 1 n; i)for(int j 0; j n; j)if(i j 1)for(int k 0; k n; k)if(i - (1 j) k 1)dp[i][j] min(dp[i][j], dp[i - (1 j)][k] value[k][j]);cout dp[(1 n) - 1][n - 1] endl;return 0;
}
