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;
}