import java.io.*;
import java.util.*;
public class cities {
static int n, k, m;
static long INF = (long)1e17;
static ArrayList<Edge>[] arr;
static int[] target;
static long[][] dp;
public static void main(String[] args) throws IOException{
FastIO file = new FastIO();
n = file.nextInt();
k = file.nextInt();
m = file.nextInt();
arr = new ArrayList[n];
for (int i=0; i<n; i++) {
arr[i] = new ArrayList<>();
}
target = new int[n];
for (int i=0; i<k; i++) {
target[i] = file.nextInt()-1;
}
for (int i=0; i<m; i++) {
int a = file.nextInt()-1;
int b = file.nextInt()-1;
int c = file.nextInt();
arr[a].add(new Edge(b, c));
arr[b].add(new Edge(a, c));
}
dp = new long[n][1<<k];
for (int i=0; i<n; i++){
Arrays.fill(dp[i], INF);
dp[i][0] = 0;
}
for (int i=0; i<k; i++){
dp[target[i]][1<<i] = 0;
}
for (int i=1; i<(1<<k); i++){
for (int j=0; j<i; j++){
if ((i | j) != i){
continue;
}
// if ((i^j) > j){
// continue;
// }
for (int v=0; v<n; v++){
dp[v][i] = Math.min(dp[v][i], dp[v][j] + dp[v][i^j]);
}
}
PriorityQueue<State> pq = new PriorityQueue<>();
for (int j=0; j<n; j++){
if (dp[j][i] != INF){
pq.add(new State(j, dp[j][i]));
}
}
boolean[] used = new boolean[n];
while (!pq.isEmpty()){
State curr = pq.poll();
if (used[curr.at]){
continue;
}
used[curr.at] = true;
for (Edge j : arr[curr.at]){
if (dp[j.to][i] > curr.cost + j.cost){
dp[j.to][i] = curr.cost + j.cost;
pq.add(new State(j.to, dp[j.to][i]));
}
}
}
}
int full = (1<<k) - 1;
long ans = INF;
for (int i=0; i<n; i++){
ans = Math.min(ans, dp[i][full]);
}
file.println(ans);
file.close();
}
static class State implements Comparable<State>{
int at;
long cost;
public State(int at, long cost){
this.at = at;
this.cost = cost;
}
public int compareTo(State o){
return Long.compare(this.cost, o.cost);
}
}
static class Edge{
int to;
long cost;
public Edge(int to, long cost){
this.to = to;
this.cost = cost;
}
}
static class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1<<16];
private int curChar, numChars;
public FastIO() { this(System.in,System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
public FastIO(String i) throws IOException {
super(System.out);
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars == -1) return -1; // end of file
}
return buf[curChar++];
}
// to read in entire lines, replace c <= ' '
// with a function that checks whether c is a line break
public String next() {
int c; do { c = nextByte(); } while (c <= ' ');
StringBuilder res = new StringBuilder();
do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
return res.toString();
}
public int nextInt() {
int c; do { c = nextByte(); } while (c <= ' ');
int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10*res+c-'0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public long nextLong() {
int c; do { c = nextByte(); } while (c <= ' ');
int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10*res+c-'0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() { return Double.parseDouble(next()); }
}
}
Compilation message
Note: cities.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
59 ms |
8468 KB |
Output is correct |
| 3 |
Correct |
60 ms |
8116 KB |
Output is correct |
| 4 |
Correct |
61 ms |
8632 KB |
Output is correct |
| 5 |
Correct |
69 ms |
8440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1562 ms |
63424 KB |
Output is correct |
| 2 |
Correct |
1527 ms |
67896 KB |
Output is correct |
| 3 |
Correct |
1192 ms |
51268 KB |
Output is correct |
| 4 |
Correct |
336 ms |
35484 KB |
Output is correct |
| 5 |
Correct |
931 ms |
52776 KB |
Output is correct |
| 6 |
Correct |
313 ms |
35372 KB |
Output is correct |
| 7 |
Correct |
156 ms |
12668 KB |
Output is correct |
| 8 |
Correct |
143 ms |
12464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
14020 KB |
Output is correct |
| 2 |
Correct |
180 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
149 ms |
14008 KB |
Output is correct |
| 4 |
Correct |
150 ms |
13004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2854 ms |
74708 KB |
Output is correct |
| 2 |
Correct |
2857 ms |
86424 KB |
Output is correct |
| 3 |
Correct |
1846 ms |
68264 KB |
Output is correct |
| 4 |
Correct |
1843 ms |
60056 KB |
Output is correct |
| 5 |
Correct |
672 ms |
42072 KB |
Output is correct |
| 6 |
Correct |
345 ms |
35756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5759 ms |
90788 KB |
Output is correct |
| 2 |
Correct |
5748 ms |
103568 KB |
Output is correct |
| 3 |
Correct |
5491 ms |
108996 KB |
Output is correct |
| 4 |
Correct |
4242 ms |
83748 KB |
Output is correct |
| 5 |
Correct |
3380 ms |
70524 KB |
Output is correct |
| 6 |
Correct |
914 ms |
42748 KB |
Output is correct |
| 7 |
Correct |
409 ms |
35636 KB |
Output is correct |
