P1690 贪婪的 Copy
P1690 贪婪的 Copy - 洛谷
题目描述
Copy 从卢牛那里听说在一片叫 yz 的神的领域埋藏着不少宝藏，于是 Copy 来到了这个被划分为 n 个区域的神地。卢牛告诉了 Copy 这里共有 n 个宝藏，分别放在第 Pi 个（1≤Pi≤n）区域。Copy 还得知了每个区域之间的距离。现在 Copy 从 1 号区域出发，要获得所有的宝藏并到 n 号区域离开。Copy 很懒，只好来找你为他寻找一条合适的线路，使得他走过的距离最短。
输入格式
第一行一个正整数 n（1≤n≤100）
接下来一个 n×n 的矩阵，第 i+1 行第 j 列的数字表示区域 i, j 之间的距离。每个距离用空格隔开，距离保证 i→j≤1000。请注意的 i→j 距离并不一定等于 j→i 的距离。
第 n+2 行一个整数 P（0≤P≤10）。
第 n+3 行共 P 个用空格隔开的整数，表示有宝藏的区域编号。
输出格式
一个整数，为 Copy 获得全部宝藏需要的最短距离。数据保证答案小于等于 231−1。
输入输出样例
输入 #1
2
0 4
5 0
2
1 2
输出 #1
4
输入 #2
3
0 2 6
1 0 4
7 10 0
1
2
输出 #2
6
说明 / 提示
- 对 30% 的数据，1≤n≤15，其余如题所述。
- 对 100% 的数据，全部数据范围如题所述。
代码：
#include<bits/stdc++.h>
using namespace std;
int n, p;
int min_total = INT_MAX;
int dis[105][105];
vector<int> treasures;
void dfs(int cur,int sum,int count,vector <bool> & vis)
{if(count == p){sum += dis[cur][n];min_total = min(min_total,sum);return ; }for(int i = 0 ; i < p ; i++){if(!vis[i]){vis[i] = true;dfs(treasures[i],sum + dis[cur][treasures[i]],count + 1,vis);vis[i] = false;}} }
int main()
{cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> dis[i][j];}}cin >> p;for (int i = 0; i < p; i++) {int t;cin >> t;treasures.push_back(t);}for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);}}}if (p == 0) {min_total = dis[1][n];} else {vector <bool> vis(n+1,0);dfs(1,0,0,vis);}cout << min_total << endl;return 0;
}#include<bits/stdc++.h>
using namespace std;
int n, p;
int dis[105][105];
vector<int> treasures;
int main()
{cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> dis[i][j];}}cin >> p;for (int i = 0; i < p; i++) {int t;cin >> t;treasures.push_back(t);}for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);}}}int min_total = INT_MAX;if (p == 0) {min_total = dis[1][n];} else {//处理当前的排列 sort(treasures.begin(), treasures.end());int cur_total = 0;int cur = 1;for (int t : treasures) {cur_total += dis[cur][t];cur = t;}cur_total += dis[cur][n];min_total = cur_total;while (next_permutation(treasures.begin(), treasures.end())) //字典序最小的排列到大 {cur_total = 0;cur = 1;for (int t : treasures){cur_total += dis[cur][t];cur = t;}cur_total += dis[cur][n];min_total = min(min_total, cur_total);}}cout << min_total << endl;return 0;
}