C++ 解法, 执行用时: 25ms, 内存消耗: 428KB, 提交时间: 2020-10-29

 #include <bits/stdc++.h>
using namespace std;

int n, k, a[101][101], b[101], Min=INT_MAX;

void DFS(int cnt, int s){
    if(cnt==2*k){
        Min = min(Min, s);
        return;
    }
    for(int i=cnt+1;i<2*k;i++){
        swap(b[i], b[cnt+1]);
        DFS(cnt+2, s+a[b[cnt]][b[cnt+1]]);
        swap(b[i], b[cnt+1]);
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d", &a[i][j]);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j && a[i][k]!=-1 && a[k][j]!=-1){
                    if(a[i][j]==-1)
                        a[i][j] = a[i][k] + a[k][j];
                    else
                        a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
                }
    scanf("%d", &k);
    for(int i=0;i<2*k;i++)
        scanf("%d", &b[i]);
    DFS(0, 0);
    printf("%d\n", Min);
    return 0;
}

C++14 解法, 执行用时: 25ms, 内存消耗: 440KB, 提交时间: 2020-10-05

#include<bits/stdc++.h>
using namespace std;
int n,k,a[101][101],b[101],Min=-1;

void DFS(int count,int ans){
    
    if(count==2*k){
        if(Min==-1){
            Min = ans;
        }
        else{
            if(Min>ans)
                Min=ans;
            
        }
        return;
    }
    for(int i =count+1;i<2*k;i++){
        swap(b[i],b[count+1]);
        DFS(count+2,ans+a[b[count]][b[count+1]]);
        swap(b[i],b[count+1]);
        
    }
    
}



int main(){
    scanf("%d",&n);
    for ( int i =1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(int k = 1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j =1;j<=n;j++){
                if(i!=j&& a[i][k]!=-1 && a[k][j]!=-1){
                    if(a[i][j]==-1)
                        a[i][j]=a[i][k]+a[k][j];
                    else
                        if(a[i][j]>a[i][k]+a[k][j])
                            a[i][j]=a[i][k]+a[k][j];
                }
            }
    scanf("%d",&k);
    for(int i =0;i<2*k;i++)
        scanf("%d",&b[i]);
    DFS(0,0);
    printf("%d\n",Min);
    return 0 ;
}