import java.io.*;
import java.util.*;
public class cities {
static int n, k, m, INF = (int)1e9;
static ArrayList<Edge>[] arr;
static int[] target;
static int[][] 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 int[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;
int 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, cost;
public State(int at, int cost){
this.at = at;
this.cost = cost;
}
public int compareTo(State o){
return this.cost - o.cost;
}
}
static class Edge{
int to, cost;
public Edge(int to, int 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 |
60 ms |
8632 KB |
Output is correct |
| 2 |
Correct |
60 ms |
8400 KB |
Output is correct |
| 3 |
Incorrect |
65 ms |
8364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
365 ms |
48124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
12164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
397 ms |
47944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
678 ms |
58296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
