Problem:


Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200

1≤M≤N×(N-1)/2

2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

Sample Output 1

2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

Sample Output 2

4

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Sample Output 3

3



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Runtime Error

Solution code:
N,M,R=map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
edge = [[] for _ in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append((b, c))
    edge[b].append((a, c))
path = [[None for _ in range(N)] for _ in range(N)]
def bfs(i):
    q = [(i,0)]
    visited = [False]*N
    visited[i] = True
    path[i][i] = 0
    while q != []:
        cur, d = q.pop(0)
        for nxt, dist in edge[cur]:
            if not visited[nxt]:
                q.append((nxt, d+dist))
                visited[nxt] = True
                path[i][nxt] = d+dist
            elif path[i][nxt] > d+dist:
                path[i][nxt] = d+dist
                q.append((nxt, d+dist))
for i in range(N):
    bfs(i)
ret = float("inf")
for j in range(R):
    ans = 0
    visited = [False]*R
    cur = r[j]
    visited[j] = True
    while not all(visited):
        d = 100000
        argmin = None
        for i in range(R):
            if not visited[i] and path[cur][r[i]] < d:
                argmin = i
                d = path[cur][r[i]]
        visited[argmin] = True
        cur = r[argmin]
        ans += d
    ret = min(ret, ans)
print(ret)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m,r=map(int,input().split())
visit=list(map(int,input().split()))
dist=[[10**9]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dist[a-1][b-1],dist[b-1][a-1]=c,c
for i in range(n):
  dist[i-1][i-1]=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      dist[j][k]=min(dist[j][i]+dist[i][k])
ans=10**9
check=permutations(visit)
for i in check:
  c=0
  for j in range(r-1):
    c+=dist[i[j]][i[j+1]]
  if c<ans:ans=c
print(ans)

Submission status: Runtime Error

Solution code:
use std::io::stdin;
use std::time::SystemTime;

#[allow(dead_code)]
fn read_line() -> String {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn read<T>() -> T
where T: std::str::FromStr
{
    read_line().parse::<T>().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T>() -> Vec<T>
where T: std::str::FromStr
{
    read_line().split(" ").map(|n| n.parse::<T>().ok().unwrap()).collect()
}

#[allow(dead_code)]
fn read_chars() -> Vec<char>
{
    read_line().chars().collect()
}

#[allow(dead_code)]
fn print_time() -> () {
    println!("{:?}", SystemTime::now());
}

#[allow(unused_variables)]
fn main() {
    let nmr: Vec<usize> = read_vec();
    let r: Vec<usize> = read_vec().iter().map(|n| n - 1usize).collect();
    let mut m: Vec<Vec<usize>> = vec![];
    for i in 0..nmr[0] {
        m.push(vec![10000000000; nmr[0]]);
    }

    for i in 0..nmr[1] {
        let abc: Vec<usize> = read_vec();
        m[abc[0] - 1][abc[1] - 1] = abc[2];
        m[abc[1] - 1][abc[0] - 1] = abc[2];
    }
    
    let min = |x, y| {
        if x < y {
            x
        } else {
            y
        }
    };
    
    for k in 0..nmr[0] {
        for i in 0..nmr[0] {
            for j in 0..nmr[0] {
                m[i][j] = min(m[i][j], m[i][k] + m[k][j]);
            }
        }
    }
    
    let mut ans = 10000000;
    dfs(nmr[2], &vec![], &r, &m, &mut ans);
    println!("{}", ans);
}

fn dfs(ma: usize, v: &Vec<usize>, r: &Vec<usize>, m: &Vec<Vec<usize>>, mut ans: &mut usize) {
    if ma == v.len() {
        let mut a = 0;
        for i in 0..ma - 1 {
            a += m[r[v[i]]][r[v[i + 1]]];
        }
        if a < *ans {
            *ans = a;
        }
    } else {
        for i in 0..ma {
            if !v.contains(&i) {
                let mut p = v.clone();
                p.push(i);
                dfs(ma, &p, r, m, ans);
            }
        }
    }
}

Submission status: Runtime Error

Solution code:
from itertools import permutations
N,M,R=map(int,input().split())
r=[int(i) for i in range(R)]
inf=10**9
d=[[inf]*N for i in range(N)]
for i in range(M):
  A,B,C=map(int,input().split())
  d[A-1][B-1]=C
  d[B-1][A-1]=C
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=inf      
for l in permutations(r):
  start=0
  for j in range(R-1):
    start+=d[l[j]-1][l[j+1]-1]
  ans=min(start,ans)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = [0]*(N+1)
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge[l] = next
                    l += 1
                    d[i][next] = d[i][q]+c
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = [0]*N
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge[l] = next
                    l += 1
                    d[i][next] = d[i][q]+c
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Submission status: Runtime Error

Solution code:
N,M,R=map(int,input().split())
INF=10**9
d=[[INF]*N for i in range(N)]
r=list(map(int,input().split()))
for i in range(M):
  A,B,C=map(int,input().split())
  d[A-1][B-1]=C
  d[B-1][A-1]=C
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=10**9
for L in permutations(r):
  temp=0
  for j in range(R-1):
    temp+=d[L[j]-1][L[j+1]-1]
  ans=min(temp,ans)
print(ans)

Submission status: Runtime Error

Solution code:
inf = float('inf')
 
n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]
 
 
ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0
 
for mm in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  ds[a][b] = c
  ds[b][a] = c
 
## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
 
 
#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))
 
 
import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))
inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

for mm in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  ds[a][b] = c
  ds[b][a] = c

## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])


#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))


import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))

Submission status: Runtime Error

Solution code:
n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


for k in range(n):
	 for i in range(n):
		 for j in range(n):
			 road_matrix[i][j]  = min(road_matrix[i][k] + road_matrix[k][j], road_matrix[i][j])


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Runtime Error

Solution code:
n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				sarching_point.append((road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			if sarching_point[k][1] not in searched_point:
				j = sarching_point[k][1]
				sarching_point = sarching_point[k+1:]
				break
	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Runtime Error

Solution code:

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1

mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Runtime Error

Solution code:
n,m,r = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):
    for v in range(1,N+1):#中間
        for g in range(1,N+1):#ゴール
            e[start][g] = min(e[start][g],e[start][v] + e[v][g])
            e[g][start] = e[start][g]
    return e[start]

cost = 0
dic = {}
for r in R:
    dic[r] = dijkstra(r,edge,n)

from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
for RR in temp:
    cost = 0
    for i in range(r-2):
        cost += dic[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
INF=float("inf")
G=[[INF]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    heapify(stack)
    reached=[0]*N
    reached[0]=1
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=heappop(stack)
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        reached[i]=1
        for j in range(N):
            if G[i][j]!=INF and reached[j]==0:
                heappush(stack,(G[i][j]+dis[i],j))
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
print(ans)

Submission status: Runtime Error

Solution code:

    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

q = queue.Queue()
for t in travels:
    q.put((
        0,
        (t,)
    ))

travels = R_LIST[:]

def dfs(cost,past):
    #print('aaa', past)
    if len(past) == len(travels):
        return cost
    
    ret = INT_MAX
    for t in travels:
        if t in past:
            continue
        
        if len(past) == 0:
            tmp_ret = dfs(0, [t])
            ret = min(ret, tmp_ret)
        else:
            next_cost = cost + shortest[past[-1]][t]
            if ret <= next_cost:
                continue

            next_past = past[:] + [t]
            tmp_ret = dfs(next_cost, next_past)
            ret = min(ret, tmp_ret)
        
    return ret

print(dfs(0, []))

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

q = queue.Queue()
for t in travels:
    q.put((
        0,
        (t,)
    ))

travels = R_LIST[:]

while not q.empty():
    past = q.get()
    if len(past[1]) == len(travels):
        ans = min(ans, past[0])
    
    for t in travels:
        if not t in past[1]:
            cost = past[0]
            #print(past[1][-1],t)
            cost += shortest[past[1][-1]][t]
            if ans <= cost:
                continue
            next_past = past[1] + (t,)
            q.put((
                cost,
                next_past
            ))
print(ans)

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
   
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

q = queue.Queue()
for t in travels:
    q.put((
        0,
        (t,)
    ))

travels = R_LIST[:]

while not q.empty():
    past = q.get()
    if len(past[1]) == len(travels):
        ans = min(ans, past[0])
    
    for t in travels:
        if not t in past[1]:
            cost = past[0]
            cost += shortest[past[1][-1]][t]
            if ans <= cost:
                continue
            next_past = past[1] + (t,)
            q.put((
                cost,
                next_past
            ))
print(ans)

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

q = queue.Queue()
for t in travels:
    q.put((
        0,
        (t,)
    ))

travels = R_LIST[:]

while not q.empty():
    past = q.get()
    if len(past[1]) == len(travels):
        ans = min(ans, past[0])
    
    for t in travels:
        if not t in past[1]:
            cost = past[0]
            cost += shortest[past[1][-1]][t]
            next_past = past[1] + (t,)
            q.put((
                cost,
                next_past
            ))
print(ans)

Submission status: Runtime Error

Solution code:
import math
import itertools

"""
The MIT License (MIT)

Copyright (c) 2017 Daniel Borowski

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""
class FibonacciHeap:

    # internal node class
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.parent = self.child = self.left = self.right = None
            self.degree = 0
            self.mark = False

    # function to iterate through a doubly linked list
    def iterate(self, head):
        node = stop = head
        flag = False
        while True:
            if node == stop and flag is True:
                break
            elif node == stop:
                flag = True
            yield node
            node = node.right

    # pointer to the head and minimum node in the root list
    root_list, min_node = None, None

    # maintain total node count in full fibonacci heap
    total_nodes = 0

    # return min node in O(1) time
    def find_min(self):
        return self.min_node

    # extract (delete) the min node from the heap in O(log n) time
    # amortized cost analysis can be found here (http://bit.ly/1ow1Clm)
    def extract_min(self):
        z = self.min_node
        if z is not None:
            if z.child is not None:
                # attach child nodes to root list
                children = [x for x in self.iterate(z.child)]
                for i in range(0, len(children)):
                    self.merge_with_root_list(children[i])
                    children[i].parent = None
            self.remove_from_root_list(z)
            # set new min node in heap
            if z == z.right:
                self.min_node = self.root_list = None
            else:
                self.min_node = z.right
                self.consolidate()
            self.total_nodes -= 1
        return z

    # insert new node into the unordered root list in O(1) time
    # returns the node so that it can be used for decrease_key later
    def insert(self, key, value=None):
        n = self.Node(key, value)
        n.left = n.right = n
        self.merge_with_root_list(n)
        if self.min_node is None or n.key < self.min_node.key:
            self.min_node = n
        self.total_nodes += 1
        return n

    # modify the key of some node in the heap in O(1) time
    def decrease_key(self, x, k):
        if k > x.key:
            return None
        x.key = k
        y = x.parent
        if y is not None and x.key < y.key:
            self.cut(x, y)
            self.cascading_cut(y)
        if x.key < self.min_node.key:
            self.min_node = x

    # merge two fibonacci heaps in O(1) time by concatenating the root lists
    # the root of the new root list becomes equal to the first list and the second
    # list is simply appended to the end (then the proper min node is determined)
    def merge(self, h2):
        H = FibonacciHeap()
        H.root_list, H.min_node = self.root_list, self.min_node
        # fix pointers when merging the two heaps
        last = h2.root_list.left
        h2.root_list.left = H.root_list.left
        H.root_list.left.right = h2.root_list
        H.root_list.left = last
        H.root_list.left.right = H.root_list
        # update min node if needed
        if h2.min_node.key < H.min_node.key:
            H.min_node = h2.min_node
        # update total nodes
        H.total_nodes = self.total_nodes + h2.total_nodes
        return H

    # if a child node becomes smaller than its parent node we
    # cut this child node off and bring it up to the root list
    def cut(self, x, y):
        self.remove_from_child_list(y, x)
        y.degree -= 1
        self.merge_with_root_list(x)
        x.parent = None
        x.mark = False

    # cascading cut of parent node to obtain good time bounds
    def cascading_cut(self, y):
        z = y.parent
        if z is not None:
            if y.mark is False:
                y.mark = True
            else:
                self.cut(y, z)
                self.cascading_cut(z)

    # combine root nodes of equal degree to consolidate the heap
    # by creating a list of unordered binomial trees
    def consolidate(self):
        A = [None] * int(math.log(self.total_nodes) * 2)
        nodes = [w for w in self.iterate(self.root_list)]
        for w in range(0, len(nodes)):
            x = nodes[w]
            d = x.degree
            while A[d] != None:
                y = A[d]
                if x.key > y.key:
                    temp = x
                    x, y = y, temp
                self.heap_link(y, x)
                A[d] = None
                d += 1
            A[d] = x
        # find new min node - no need to reconstruct new root list below
        # because root list was iteratively changing as we were moving
        # nodes around in the above loop
        for i in range(0, len(A)):
            if A[i] is not None:
                if A[i].key <= self.min_node.key:
                    self.min_node = A[i]

    # actual linking of one node to another in the root list
    # while also updating the child linked list
    def heap_link(self, y, x):
        self.remove_from_root_list(y)
        y.left = y.right = y
        self.merge_with_child_list(x, y)
        x.degree += 1
        y.parent = x
        y.mark = False

    # merge a node with the doubly linked root list
    def merge_with_root_list(self, node):
        if self.root_list is None:
            self.root_list = node
        else:
            node.right = self.root_list.right
            node.left = self.root_list
            self.root_list.right.left = node
            self.root_list.right = node

    # merge a node with the doubly linked child list of a root node
    def merge_with_child_list(self, parent, node):
        if parent.child is None:
            parent.child = node
        else:
            node.right = parent.child.right
            node.left = parent.child
            parent.child.right.left = node
            parent.child.right = node

    # remove a node from the doubly linked root list
    def remove_from_root_list(self, node):
        if node == self.root_list:
            self.root_list = node.right
        node.left.right = node.right
        node.right.left = node.left

    # remove a node from the doubly linked child list
    def remove_from_child_list(self, parent, node):
        if parent.child == parent.child.right:
            parent.child = None
        elif parent.child == node:
            parent.child = node.right
            node.right.parent = parent
        node.left.right = node.right
        node.right.left = node.left

class Graph:
    class Edge:
        def __init__(self, start, end, distance):
            self.start = start
            self.end = end
            self.distance = distance

    def __init__(self, size):
        self.edges = {i: {} for i in range(size)}

    def size(self):
        return len(self.edges)

    def insert_edge(self, start, end, distance):
        self.edges[start][end] = distance
        self.edges[end][start] = distance

    def dijkstra(self, s):
        d = [0 if i == s else float("inf") for i in range(self.size())]
        Q = FibonacciHeap()
        nodes = [Q.insert(d[i], i) for i in range(self.size())]

        while Q.total_nodes > 0:
            u = Q.extract_min().value
            for v, l in self.edges[u].items():
                alt = d[u] + l
                if d[v] > alt:
                    d[v] = alt
                    Q.decrease_key(nodes[v], alt)

        return d

class Path:
    def __init__(self, start, end, distance):
        self.start = start
        self.end = end
        self.distance = distance

N, M, R = (int(c) for c in input().split())
r = [int(c) - 1 for c in input().split()]
A, B, C = (list(t) for t in zip(*((lambda c1, c2, c3: (int(c1) - 1, int(c2) - 1, int(c3)))(*input().split()) for i in range(M))))

graph = Graph(N)
for i in range(M):
    graph.insert_edge(A[i], B[i], C[i])

distances = [(lambda d: [d[r_j] for r_j in r])(graph.dijkstra(r_i)) for r_i in r]

print(min(sum(distances[travel[i]][travel[i + 1]] for i in range(R - 1)) for travel in itertools.permutations(range(R))))