【SSL】2021

SSL】2021"/>

【SSL】2021

快速链接

• 原题网址
• 题目描述
• 格式
• • 输入格式
  • 输出格式
• 样例
• • 输入样例
  • 输出样例
• 解题思路
• Code

原题网址

由于某些原因，这个网址会进不去…

1370.售货员的难题 - 原题网址

题目描述

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

格式

输入格式

村庄数 n n n和各村之间的路程（均是整数）。

输出格式

最短路程

样例

输入样例

3
0 2 1
1 0 2
2 1 0

第 1 1 1行表示村庄数量 n n n；
第 2 2 2行表示村庄 1 1 1到各村的路程。

输出样例

3

解题思路

这道题用了 d f s dfs dfs（深度优先搜索），而这里需要 3 3 3个参数，分别是： i n t d e p int\ dep int dep表示当前已经走完了几个村庄，而当 d e p = n dep=n dep=n时，表示当前在最后一个村庄，需要立即返回村庄 1 1 1，特殊处理后 r e t u r n return return；第二个参数 i n t m int\ m int m表示当前在哪个村庄；第三个参数 i n t a s int\ as int as则表示当前已经走了的路程。

Code

#include<iostream>
#include<cstring>
#define maxn 40
using namespace std;
int n, s[maxn + 1][maxn + 1], ans = 2147483647;
int w[maxn + 1];
void input() // 输入 
{cin>>n;for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cin>>s[i][j];
}void dfs(int dep, int m, int as) // dep表示当前走完了几个村庄，m表示当前所在村庄，as表示走了的路程 
{if (dep == n){as += s[m][1];if (as < ans) ans = as;return;}if (as + (n - dep + 1) > ans) return;for (int i = 1; i <= n; i ++){if(i==m) continue; if (!w[i]){w[i] = 1;dfs(dep + 1, i, as+s[m][i]);w[i] = 0;}}
}void output()
{cout<<ans;
}int main()
{input();w[1] = 1;dfs(1, 1, 0);output();return 0;
}

大功告成 ∼ \sim ∼