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:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <climits>
using namespace std;
int minDis[201][201];
int edge[201][201];
int mark[201];
int city[8];
bool cityMark[8];
int n,m;
int r;
int a,b,c;
int cnt;

/*
int dfs(int x)
{
    int tmp;
    if(x==r){
        tmp = 0;
        for
    }
    return min(tmp,dfs(x+1));
}
*/
void floyd()
{
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++){
            minDis[i][j] = min(edge[i][j],minDis[i][j]);
        }
    for(int k = 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++){
                if(minDis[i][j]>minDis[i][k]+minDis[k][j]){
                    minDis[i][j] = minDis[i][k]+minDis[k][j];
                }
            }
}
void printall()
{
    cout<<"--------"<<endl;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cout<<edge[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cout<<minDis[i][j]<<" ";
        }
        cout<<endl;
    }
}
int solve()
{
    floyd();
    //printall();
    sort(city,city+r);
    int R = INT_MAX;
    int tmp;
    do{
        tmp = 0; 
        for(int i = 0;i<r-1;i++){
            //cout<<city[i]<<" ";
            tmp+=minDis[city[i]][city[i+1]];
        }
        R = min(R,tmp);
    }while(next_permutation(city,city+r));
    return R;
}
int main()
{
    for(int i = 0;i<201;i++)
        for(int j = 0;j<201;j++){
            if(i == j){
                edge[i][j] = 0;
                minDis[i][j] = 0;
            }
            else{
                edge[i][j] = INT_MAX;
                minDis[i][j] = INT_MAX;
            }
        }
    cin>>n>>m>>r;
    for(int i=0;i<r;i++)cin>>city[i];
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        edge[a][b] = c;
        edge[b][a] = c; 
    }
    int res = solve();
    cout<<res<<endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
from itertools import permutations 
inf=10**9
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n-1):
        for j in range(i, n):
            dk=d[i][k]+d[k][j]
            if d[i][j]>dk:
                d[j][i]=dk
                d[i][j]=dk
permutations(r)
ans=inf
p=list(permutations(r))
for pi in p:
    res=0
    for i in range(r1-1):
        res+=d[pi[i]-1][pi[I+1]-1]
    if ans>res:
        ans=res
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations 
inf=10**9
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n-1):
        for j in range(i, n):
            dk=d[i][k]+d[k][j]
            if d[i][j]>dk:
                d[j][i]=dk
                d[i][j]=dk
permutations(r)
ans=inf
for pi in permutations(r):
    res=0
    for i in range(r1-1):
        res+=d[pi[i]-1][pi[I+1]-1]
    if ans>res:
        ans=res
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations 
inf=10**9
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n-1):
        for j in range(i, n):
            d[i][j]=min(d[i][j], d[i][k]+d[k][j])
            d[j][i]=d[i][j]
p=list(permutations(r))
ans=inf
for pi in p:
    res=0
    for i in range(r1-1):
        res+=d[pi[i]-1][pi[I+1]-1]
    if ans>res:
        ans=res
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations 
inf=10**10
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n):
        for j in range(i, n):
            d[i][j]=min(d[i][j], d[i][k]+d[k][j])
            d[j][i]=d[i][j]
p=list(permutations(r))
ans=inf
for pi in p:
    res=0
    for i in range(r1-1):
        res+=d[pi[i]-1][pi[I+1]-1]
    ans=min(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations 
inf=10**10
n, m, r1 = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n):
        for j in range(i, n):
            d[i][j]=min(d[i][j], d[i][k]+d[k][j])
            d[j][i]=d[i][j]
p=list(permutations(r))
ans=inf
for pi in p:
    res=0
    for i in range(r1-1)
        res+=d[pi[i]-1][pi[I+1]-1]
    ans=min(ans, res)
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()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
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])
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

Submission status: Runtime Error

Solution code:
from itertools import permutations as pe
n,m,r=map(int,input().split())
s=[[(0 if i==j else float("inf"))for j in range(n+1)]for i in range(n+1)]
g=list(pe(list(map(int,input().split()))))
for i in range(n):
    a,b,c=map(int,input().split())
    s[a][b]=c
    s[b][a]=c
for h in range(n):
    for i in range(n):
        for j in range(n):
            if s[i][j]>s[i][h]+s[h][j]:
                s[i][j]=s[i][h]+s[h][j]
k=float("inf")
for i in range(len(g)):
    d=g[i]
    c=0
    for j in range(1,len(d)):
        c+=s[d[j-1]][d[j]]
        if c>k:
            break
    else:
        k=min(c,k)
print(k)

Submission status: Runtime Error

Solution code:
from itertools import permutations as per

n,m,r = map(int,input().split())
rlist = list(map(int,input().split()))
ans = 10**9
A = [[10**8]*n for _ in range(n)]
for _ in range(n):
  a,b,c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c

for i in range(n-1):
  for j in range(i+1,n):
    for k in range(n):
      newd = A[i][k] + A[k][j]
      if A[i][j] > newd:
        A[i][j] = newd
        A[j][i] = newd
for x in per(rlist):
  cost = 0
  for i in range(r-1):
    cost += A[x[i]-1][x[i+1]-1]
  if cost < ans:
    ans = cost
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutation as per

n,m,r = map(int,input().split())
rlist = list(map(int,input().split()))
ans = 10**9
A = [[10**8]*n for _ in range(n)]
for _ in range(n):
  a,b,c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c

for i in range(n-1):
  for j in range(i+1,n):
    for k in range(n):
      newd = A[i][k] + A[k][j]
      if A[i][j] > newd:
        A[i][j] = newd
        A[j][i] = newd
for x in per(rlist):
  cost = 0
  for i in range(r-1):
    cost += A[x[i]-1][x[i+1]-1]
  if cost < ans:
    ans = cost
print(ans)

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
rs = permutations(map(lambda x: int(x) - 1, input().split()))
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in rs:
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)

Submission status: Runtime Error

Solution code:
#074-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
from itertools import permutations
n,m,r=IL()
rl=IL()
cost=[[float("INF") for i in range(n)] for j in range(n)]
for i in range(m):
    f,t,c=IL()
    cost[f][t]=c
    cost[t][f]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])

perm=permutations(r)
ans=float("INF")
for path in perm:
    t=0
    for i in range(7):
        t+=cost[rl[path[i]]][rl[path[i+1]]]
    ans=min(ans,t)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
import sys


input = sys.stdin.readline


N, M, R = map(int, input().split())
dest = [x-1 for x in map(int, input().split())]

inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    mat[a-1][b-1] = mat[b-1][a-1] = c


def war(g):
    ran = range(N)
    for i in ran:
        for j in ran:
            for k in ran:
                mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])


ans = inf
mat = war(mat)
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
        if tmp > ans:
            break
    ans = min(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
import sys


input = sys.stdin.readline


N, M, R = (list)(map(int, input().split()))

#dest = (list)(map(lambda x: (int)(x)-1, input().split()))
dest = [x-1 for x in input().split()]


inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = (list)(map(int, input().split()))
    mat[a-1][b-1] = mat[b-1][a-1] = c


for i in range(N):
    for j in range(N):
        for k in range(N):
            mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
    ans = min(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
import  scipy as sp 
from itertools import permutations
n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c

s=sp.sparse.csgraph.floyd_warshall(s)   
ans=float('inf')
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Submission status: Runtime Error

Solution code:
import sys,itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in sys.stdin];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r))

Submission status: Runtime Error

Solution code:
#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

rperm=n_perm(rlis)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)
    
print(ans)

Submission status: Runtime Error

Solution code:
#dojkstra (prioroty queue ver.)
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき

def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

rperm=n_perm(rlis)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)
    
print(ans)

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]
import heapq
from itertools import permutations

N, M, R = inpl()
r = inpl()
inf = 10**11
Q = [[inf] * N for _ in range(N)]
path = [[0] * N for _ in range(N)]

for i in range(M):
    A,B,C = inpl()
    path[A-1][B-1] = path[B-1][A-1] = C

for i in r:
    decided = [False for _ in range(N)]
    H = []
    ctr = 0
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    for _ in range(N):
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                break
        for j in range(N):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

Ans = inf
for i in permutations(r):
    ans = 0
    for j in range(R-1):
        ans += Q[i[j]-1][i[j+1]-1]
    Ans = min(Ans,ans) 
        
print(Ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
if ans==float('inf'):
    print(0)
else:
    print(int(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
print(int(ans))

Submission status: Runtime Error

Solution code:
import numpy as np

def search(now,r,dist,ans):
    print(r,ans)
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])
print(dist)
ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
print(int(ans))

Submission status: Runtime Error

Solution code:
def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    #root = [[1000000000 for i in range(N)] for i in range(N)]
    #for i, j, k in ABC:
     #   root[i - 1][j - 1] = k
      #  root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替えのタプル
        return itertools.permutations(list_name, len(list_name))

    for i in range(N):
        for j in range(N):
            for k in range(N):
                root[i][j] = min(root[i][j], root[i][k] + root[k][j])
    #a = kumiawase(r)
    #ans = 10000000000
    #for i in a:
     #   key = 0
      #  for j in range(len(i) - 1):
       #     key += root[i[j] - 1][i[j + 1] - 1]
        #ans = min(ans, key)
    #print(ans)
ABC073D()

Submission status: Runtime Error

Solution code:
    import itertools

    def kumiawase(list_name):  # list_name(リスト)のすべての並び替えのタプル
        return itertools.permutations(list_name, len(list_name))

    for i in range(N):
        for j in range(N):
            for k in range(N):
                root[i][j] = min(root[i][j], root[i][k] + root[k][j])
    #a = kumiawase(r)
    #ans = 10000000000
    #for i in a:
     #   key = 0
      #  for j in range(len(i) - 1):
       #     key += root[i[j] - 1][i[j + 1] - 1]
        #ans = min(ans, key)
    #print(ans)
ABC073D()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(j+1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.product(rarray,repeat=len(rarray)):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
#input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(j+1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.product(rarray,len(rarray)):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
#input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]]
            #adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Runtime Error

Solution code:
from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

for k in range(1, n+1):
    for i in r:
        for j in r:
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))

Submission status: Runtime Error

Solution code:
from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

for k in range(n):
    for i in r:
        for j in r:
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))

Submission status: Runtime Error

Solution code:
from itertools import permutations

inf = float("inf")
n,m,r = map(int,raw_input().split())
arr = map(int,raw_input().split())
x = range(n)
d = [[inf for i in x] for j in x]

for i in range(n):
	d[i][i] = 0

for i in x:
	f,t,c = map(int,raw_input().split())
	d[f-1][t-1] = c
	d[t-1][f-1] = c



for i in x:
	for j in x:
		for k in x:
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])


ans = inf
for i in permutations(arr):
	distance = 0
	for j in range(r-1):
		distance += d[i[j]-1][i[j+1]-1]

	ans = min(ans,distance)

print ans

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.shortest_path(A,method='D')

s=min(sum([A[i][j] for i,j in zip(a[:-1],a[1:])]) for a in pm(r))
print(int(s))

Submission status: Runtime Error

Solution code:
N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

dis=[[100001 for i in range(N+1)]]

for i in range(N):
  dis.append([100001 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

for i in range(1,N+1):
  dis[i][i]=0




from itertools import permutations
mi=1000000
BASH=[]
for item in permutations([int(i) for i in range(1,M+1)]):
    BASH.append(list(item))

for i in BASH:

  p=0
  for j in range(0,len(i)-1):
    p+=dis[i[j]][i[j+1]]
  mi=min(mi,p)
print(mi)

Submission status: Runtime Error

Solution code:
def permutation(a, i):
    if i==len(a):
        tmp=0
        check=[]
        for k in range(len(a)-1):
            boo=False
            tmp+=dis[a[k]-1][a[k+1]-1]
            check.append(int(a[k]))
            check.append(int(a[k+1]))
            check.sort()
            global town
            ind=0
            while ind<len(town):
                if str(town[-1])==str(check[-1]):
                    if ind==len(town)-1:
                        boo=True
                ind+=1
            k+=1
            if boo==True:
                break
        global ans
        ans=min(ans,tmp)
    else:
        for j in range(i, len(a)):
            a[j],a[i]=a[i],a[j]
            permutation(a, i+1)
            a[j],a[i]=a[i],a[j]
nmr=input().split()
n=int(nmr[0])
m=int(nmr[1])
r=int(nmr[2])
ans=9999999999999999
tmp=0
town=input().split()

town.sort()
to=[i for i in range(1,n+1)]
for i in range(len(to)):
    to[i]=int(to[i])
    i+=1
dis=[[0]*m for i in range(m)]
for i in range(m):
    x=input().split()
    dis[int(x[0])-1][int(x[1])-1]=int(x[2])
    dis[int(x[1])-1][int(x[0])-1]=int(x[2])
permutation(to, 0)
print(ans)

Submission status: Runtime Error

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=inf


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Runtime Error

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=math.inf


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Runtime Error

Solution code:
from itertools import permutations

def hoge():
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  r = [x - 1 for x in r]
  inf = float('inf')
  d = [[inf] * N for i in range(N)]

  for i in range(N):
      d[i][i] = 0

  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):
              t = d[i][k] + d[k][j]
              if d[i][j] > t:
                d[i][j] = t


  ans = inf
  for i in permutations(r):
      tmphoge = len(i) - 1
      temp = 0
      for j in range(tmphoge):
          temp += d[i[j]][i[j+1]]
          if temp > ans:
              break
      if ans > temp:
        ans = tmp
      # ans = min(ans, temp)

  print(ans)
hoge()