友好城市

/**
floyd完后，需要枚举这2k个点的k种边的组合。
对每条边，只需要固定起点，枚举终点即可。
因为起点和终点互换后还是相同的边。
注释部分掉的部分写的比较啰嗦，因为对全排列不太熟悉。

**/

/**
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int[][] A;
    private static int[] cities;
    private static int result = Integer.MAX_VALUE;
    private static int k;
    static boolean[] vis;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        A = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                A[i][j] = in.nextInt();
                if(A[i][j] == -1)A[i][j] = 0x3f3f3f3f;
            }
        }
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    A[i][j] = Math.min(A[i][j],A[i][k]+A[k][j]);
                }
            }
        }
        k = in.nextInt();
        cities = new int[2*k];
        for(int i=0;i<2*k;i++)cities[i] = in.nextInt()-1;
        vis = new boolean[16];
        dfs(0,new ArrayList<>());
        System.out.println(result);

    }

 
    //枚举第k条边时，所选的边集为t
  
    static void dfs(int i,ArrayList<Integer> t){
        if(i==k){
            int cur = 0;
            for(int s=0;s<2*k;s+=2){//计算答案
                cur+=A[t.get(s)][t.get(s+1)];
            }
            result = Math.min(cur,result);
            return;
        }
        int s = 0; //找到一个没使用过的作为起点
        for(;s<2*k;s++){
            if(!vis[s])break;//边的起点
        }
        vis[s]=true;
        t.add(cities[s]);
        for(int j=0;j<2*k;j++){//枚举边的终点
            if(vis[j])continue;
            vis[j] = true;
            t.add(cities[j]);
            dfs(i+1,t);//枚举下一条边。
            vis[j]=false;
            t.remove(t.size()-1);
        }
        vis[s] = false;
        t.remove(t.size()-1);
    }
}

**/

import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int[][] A;
    private static int[] cities;
    private static int result = Integer.MAX_VALUE;
    private static int k;
    static int vis;
    public static void main(String[] args)throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());
       String[] strs;
        A = new int[n][n];
        for (int i = 0; i < n; i++) {
            strs = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                A[i][j]=Integer.parseInt(strs[j]);
                if (A[i][j] == -1)A[i][j] = 0x3f3f3f3f;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    A[i][j] = Math.min(A[i][j], A[i][k] + A[k][j]);
                }
            }
        }
        k = Integer.parseInt(br.readLine());
        strs = br.readLine().split(" ");
        cities = new int[k<<1];
        for (int i = 0; i < 2 * k; i++)cities[i] = Integer.parseInt(strs[i])-1;
        vis = (1<<2*k)-1; 
        dfs(0, 0);
        System.out.println(result);

    }

    /**
    枚举k条边,vis 0代表访问过 1 代表没访问过
    */
    static void dfs(int i, int cur) {
        if (cur >= result) return;
        if (i == k) {
            result = Math.min(cur, result);
            return;
        }
        int s = 0;
         //vis  最近的1
        s = Integer.numberOfTrailingZeros(vis);
        vis-=(1<<s);
        for (int j = s+1; j < 2 * k; j++) {
            if (((vis>>j)&1)==0)continue;
            vis-=(1<<j);
            cur += A[cities[s]][cities[j]];
            dfs(i + 1, cur); //枚举下一条边。
            vis+=(1<<j);
            cur -= A[cities[s]][cities[j]];
        }
        vis+=(1<<s);
    }
}