1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
import java.util.*;

// A0087884H
// Lim Jiew Meng

class Supermarket {
  private int N; // number of items in the supermarket. V = N+1 
  private int K; // the number of items that Steven has to buy
  private int[] shoppingList; // indices of items that Steven has to buy
  private int[][] T; // the complete weighted graph that measures the direct walking time to go from one point to another point in seconds
  

  private HashMap<Integer, HashMap<Integer, Integer>> memo; // memo of TSP(source, visited)
  private HashMap<Integer, HashMap<Integer, Integer>> sssp; // sssp of any 2 required nodes and source

  public Supermarket() {
    
  }

  int Query() {
    memo = new HashMap<Integer, HashMap<Integer, Integer>>();
    sssp = new HashMap<Integer, HashMap<Integer, Integer>>();
    
    // preprocess: compute sssp between any 2 nodes/source
    int node1, node2;
    for (int i = 0; i < K+1; i++) { 
      HashMap<Integer, Integer> tmp = new HashMap<Integer, Integer>();
      node1 = i;
      if (node1 != 0) {
        node1 = shoppingList[i-1];
      }

      for (int j = 0; j < K+1; j++) {
        // find shortest part between any 2 shopping list items (i-1 | j-1) and source (0)
        node2 = j;
        if (node2 != 0) {
          node2 = shoppingList[j-1];
        }

        if (node1 != node2) {
          tmp.put(node2, dijkstra(node1, node2));
        } else {
          tmp.put(node2, 0);
        }
        System.out.println("SP from " + node1 + " to " + node2 + " is " + tmp.get(node2));
      }

      // 2D HashMap for shortest path between any 2 shopping item and source. eg.
      //    | 0  1  4  7
      //  --+-------------
      //  0 |  
      //  1 |
      //  4 | 
      //  7 |
      sssp.put(node1, tmp);
    }

    // actual query
    return TSP(0, 0);
  }

  int TSP(int source, int visited) {
    //System.out.println("source/visited = " + source + " / " + visited);
    //System.out.println(visited + " =? " + ((int)(Math.pow(2, K)-1)));
     if (visited == (int)(Math.pow(2, K)-1)) { // all required visited
      System.out.println("TSP (all) " + source + ", visited: " + visitedString(visited) + " = " + sssp.get(source).get(0));
      return sssp.get(source).get(0); // return to source (0)
    } else if (memo.containsKey(source) && memo.get(source).containsKey(visited)) {
      System.out.println("TSP (DP) " + source + ", visited: " + visitedString(visited) + " = " + memo.get(source).get(visited));
      return memo.get(source).get(visited);
    } else {
      int item;
      if (!memo.containsKey(source)) {
        memo.put(source, new HashMap<Integer, Integer>());
      }
      memo.get(source).put(visited, 1000000);
      for (int v = 0; v < K; v++) {
        item = shoppingList[v];
        if (!hasVisited(visited, item)) {
          //System.out.println("trying to mark " + v + " as visited");
          memo.get(source).put(visited, Math.min(
            memo.get(source).get(visited),
            sssp.get(source).get(item) + TSP(item, visit(visited, v))
          ));
          //System.out.println("Considering: " + source + " to " + visited + "=" + memo[source][visited] + " vs " + SPBetItems.get(source).get(item) + TSP(item, visit(visited, item)));
        }
      }
      System.out.println("TSP " + source + ", visited: " + visitedString(visited) + " = " + memo.get(source).get(visited));
      return memo.get(source).get(visited);
    }
  }

  int dijkstra(int src, int dest) {
    //System.out.println("====== DIJKSTRA from " + src + " to " + dest);
    PriorityQueue<IntegerPair> PQ = new PriorityQueue<IntegerPair>();
    HashMap<Integer, Integer> dist = new HashMap<Integer, Integer>(); // shortest known dist from {src} to {node}
    // init shortest known distance
    for (int i = 0; i < N+1; i++) {
      if (i != src) {
        dist.put(i, Integer.MAX_VALUE); // dist to any {i} is big(unknown) by default
      } else {
        dist.put(src, 0); // dist to {src} is always 0
      }
    }
    IntegerPair node;
    int nodeDist;
    int nodeIndex;

    PQ.offer(new IntegerPair(0, src)); 
    while (PQ.size() > 0) {
      node = PQ.poll();
      nodeDist = node.first();
      nodeIndex = node.second();

      if (nodeDist == dist.get(nodeIndex)) {
        // process out going edges
        //System.out.println("DIJKSTRA polled: { " + nodeDist + ", " + nodeIndex + " }");
        for (int v = 0; v < N+1; v++) { // since its a complete graph, process all edges
          if (v != nodeIndex) { // except curr node
            if (dist.get(v) > dist.get(nodeIndex) + T[nodeIndex][v]) { // relax if possible
              dist.put(v, dist.get(nodeIndex) + T[nodeIndex][v]);
              PQ.offer(new IntegerPair(dist.get(v), v));
              //System.out.println("DIJKSTRA new: { " + v + ", " + dist.get(v) + " }");
            }
          }
        }
      }
    }
    return dist.get(dest);
  }

  int visit(int visited, int node) {
    //System.out.println(">> marking " + node + " becomes " + Integer.toBinaryString(visited | (1 << node)));
    return visited | (1 << node);
  }

  boolean hasVisited(int visited, int node) {
    return (visited & (1 << node)) == (1 << node);
  }

  String visitedString(int visited) {
    String visitedStr = "";
    String binaryString = Integer.toBinaryString(visited);
    //System.out.println("binary visited: \""+ visited + "=" + binaryString + "\"");
    char[] chars = binaryString.toCharArray();
    for (int i = 0; i < chars.length; i++) {
      if (chars[i] == '1') {
        visitedStr += shoppingList[i] + " ";
      }
    }
    return visitedStr;
  }

  
  void run() {
    // do not alter this method
    Scanner sc = new Scanner(System.in);

    int TC = sc.nextInt(); // there will be several test cases
    while (TC-- > 0) {
      // read the information of the complete graph with N+1 vertices
      N = sc.nextInt(); K = sc.nextInt(); // K is the number of items to be bought

      shoppingList = new int[K];
      for (int i = 0; i < K; i++)
        shoppingList[i] = sc.nextInt();

      T = new int[N+1][N+1];
      for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++)
          T[i][j] = sc.nextInt();

      System.out.println(Query());
    }
  }

  public static void main(String[] args) {
    // do not alter this method
    Supermarket ps7 = new Supermarket();
    ps7.run();
  }
}

class IntegerPair implements Comparable {
  Integer _first, _second;

  public IntegerPair(Integer f, Integer s) {
    _first = f;
    _second = s;
  }

  public int compareTo(Object o) {
    if (this.first() != ((IntegerPair)o).first())
      return this.first() - ((IntegerPair)o).first();
    else
      return this.second() - ((IntegerPair)o).second();
  }

  Integer first() { return _first; }
  Integer second() { return _second; }
}