洛谷 P1690 贪婪的Copy

题目

本题难度较低，操作比较简单，首先对于范围较小的N(<=100)，我们可以先跑一遍floyd，求出任意两点之间的最短路。对于很小的p(<=15),我们可以直接考虑全排列，运用到next_permutation(, )函数即可快速解决此题

Code：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

//Mystery_Sky

//

#define maxn 300

#define INF 0x3f3f3f3f

int point[maxn];

int road[maxn][maxn];

int vis[maxn];

int ans = INF, sum;

int n, w, a, p;

void dfs(int step, int dis, int get)

{

    vis[step] = 1;

    if(get == p && step == n) {

        ans = min(dis, ans);

        return;

    }

    for(int i = 1; i <= n; i++) {

        if(i == step) continue;

        if(!vis[i] && point[i]) {

            dis += road[step][i];

            vis[i] = 1;

            dfs(i, dis, get+1);

            vis[i] = 0;

            dis -= road[step][i];

        }

    }

}

int main() {

    scanf("%d", &n);

    for(int i = 1; i <= n; i++) {

        for(int j = 1; j <= n; j++) {

            scanf("%d", &w);

            road[i][j] = w;

        }

    }

    for(int k = 1; k <= n; k++) {

        for(int i = 1; i <= n; i++) {

            for(int j = 1; j <= n; j++) {

                road[i][j] = min(road[i][j], road[i][k] + road[k][j]);

            }

        }

    }

    scanf("%d", &p);

    for(int i = 1; i <= p; i++)	scanf("%d", &point[i]);

    sort(point+1, point+1+p);

    do {

    	sum = road[1][point[1]];

    	for(int i = 2; i <= p; i++) {

    		sum += road[point[i-1]][point[i]];

		}

		sum += road[point[p]][n];

		ans = min(ans, sum);

	} while(next_permutation(point+1, point+p+1));//p!枚举全排列即可

    printf("%d\n", ans);

    return 0;

}