牛客算法周周练7 A--收集纸片(暴力枚举+全排列函数)

地址：https://ac.nowcoder.com/acm/contest/5713/A

 解析：

n=10，最多是n!种不同的排列方式。

所以可以暴力枚举每一种情况：next_permutation()；

id[]记录每个点的标号，对它进行全排列。d[i][j]表示i点到j点的距离，枚举所有情况。

对于每次全排列，求出本排列所得的距离，更新。

#include<bits/stdc++.h>
#include<map>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int a[12][12],d[12][12];
int id[12];
int n , m ,k;
int minn;
void ac()
{
    int sum=d[0][id[1]];
    for(int i=1;i<k;i++)
        {
            sum+=d[id[i]][id[i+1]];
            if(sum>minn)
                return ;
        }
    minn=min(minn,sum+d[id[k]][0]);
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        
        id[0]=0;
        minn=1e9;
        cin>>n>>m;
        cin>>a[0][0]>>a[0][1];
        cin>>k;
        for(int i=1;i<=k;i++)
            {
                cin>>a[i][0]>>a[i][1];
                id[i]=i;
            }
        for(int i=0;i<=k;i++)
            for(int j=0;j<=k;j++)
                {
                    d[i][j]=abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]);
                }
        do{
            ac();
        }while(next_permutation(id+1,id+1+k));
        printf("The shortest path has length %d
",minn);
    }
}