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: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):

        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))

        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            #print(unused)
            #print(X,total_cost)
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                #G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    N,M,R=spaceinput()
    r=spaceinput()

    g=myGraph()


    for i in range(10**9):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),ss[2])


    g2=myGraph()
    for sr in r:
        ds=g.dijkstra(sr)

        for d in ds:
            g2.add_edge((sr,d),ds[d])

    import itertools as it

    minl=10*12
    for pm in it.permutations(r):
        l=0
        for i in range(1,len(pm)):
            l+=g2.adj[pm[i-1]][pm[i]]


        if l<minl:
            minl=l


    print(minl)

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):

        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],X[0],u))

        total_cost=0
        used={n:False for n in nodes}
        used[X[0]]=True
        while True:
            #print(unused)
            #print(X,total_cost)
            cost,u,v=heapq.heappop(unused)
            if used[v]:
                continue
            X.append(v)
            used[v]=True
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if used[u]:
                    continue
                heapq.heappush(unused,(self.adj[u][v],v,u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                #G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    N,M,R=spaceinput()
    r=spaceinput()

    g=myGraph()


    for i in range(999):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),ss[2])


    g2=myGraph()
    for sr in r:
        ds=g.dijkstra(sr)

        for d in ds:
            g2.add_edge((sr,d),ds[d])

    import itertools as it

    minl=10**9
    for pm in it.permutations(r):
        l=0
        for i in range(1,len(pm)):
            l+=g2.adj[pm[i-1]][pm[i]]


        if l<minl:
            minl=l


    print(minl)

Submission status: Wrong Answer

Solution code:
import itertools

n, m, r = map(int, input().split())
order = list(map(int, input().split()))
dist = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    dist[i][i] = 0

for _ 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 range(1, n + 1):
        if dist[i][k] == -1:
            continue
        for j in range(1, n + 1):
            if dist[k][j] == -1:
                continue

            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
for perm in itertools.permutations(order):
    cur = 0
    for i in range(1, r):
        cur += dist[perm[i - 1]][perm[i]]

    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def solve(links, rs):
    visited = set()
    visited_r = 0
    lrs = len(rs)
    srs = set(rs)
    queue = [(0, rs[0])]

    while queue:
        cost, node = heappop(queue)
        if node in visited:
            continue
        if node in srs:
            visited_r += 1
        if visited_r == lrs:
            return cost
        visited.add(node)
        for c, a in links[node]:
            if a not in visited:
                heappush(queue, (cost + c, a))


n, m, r = map(int, input().split())
rs = [i - 1 for i in map(int, input().split())]
links = [set() for _ in range(n)]
for a, b, c in (map(int, input().split()) for _ in range(m)):
    a -= 1
    b -= 1
    links[a].add((c, b))
    links[b].add((c, a))

print(solve(links, rs))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

INF = 10**9
cost = [[INF]*N for _ in range(N)]
for _ in range(M):
  A, B, C = map(int, input().split())
  A -= 1
  B -= 1
  cost[A][B] = C
  cost[B][A] = 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])

ans = INF

for route in permutations(r):
  temp = 0
  for i in range(R-1):
    temp += cost[route[i]][route[i+1]]
  ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,r=map(int,input().split())
road=list(map(int,input().split()))
cost=[[float("inf")]*n for i in range(n)]
for i in range(n):
    cost[i][i]=0
for i in range(m):
    
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    cost[a][b]=c
    cost[b][a]=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])
import itertools
ans=float("inf")
for i in itertools.permutations(road):
    tmp=0
    for j in range(len(i)-1):
        tmp+=cost[i[j]-1][i[j+1]-1]
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
edges = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b,c))
    edges[b].append((a,c))
V = N
INF = float("inf")
dp = [[INF]*V for _ in range(V)]
for i in range(V):
    for j, w in edges[i]:
        dp[i][j] = w
for k in range(V):
    for i in range(V):
        for j in range(V):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
for i in range(R):
  r[i] -= 1
g = [[10 ** 8] * N for i in range(N)]
for i in range(M):
  A,B,C = map(int,input().split())
  A -= 1 
  B -= 1
  g[A][B] = C
  g[B][A] = C
def warchall_floyd(n):
  for i in range(n):
    #経由する頂点
    for j in range(n):
      #始点
      for k in range(n):
        #終点
        g[j][k] = min(g[j][k],g[j][i]+g[i][k])
        
warchall_floyd(N)
ans = float('inf')
for i in permutations(r):
  now = 0
  for j in range(R-1):
    now += g[i[j]][i[j+1]]
  if now < ans:
    ans = now
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,R=map(int,input().split())
r=list(map(int,input().split()))

d=[[float("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
  
#ワーシャルフロイド法
#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])

      
from itertools import permutations
per=list(permutations(r,R))

ans=float("INF")
for l in per:
  cnt=0
  for j in range(R-1):
    cnt+=d[l[j]-1][l[j+1]-1]
  ans=min(cnt,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m,R = i_map()
    r = i_list()
    c = [[INF]*n for i in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b,d = i_map()
        a -= 1
        b -= 1
        c[a][b] = c[b][a] = d

    for k in range(n): # 経由
        for i in range(n): # 始点
            for j in range(n): # 終点
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])

    r = list(itertools.permutations(r, R))

    ans = INF
    for i in r:
        trial = 0
        for k in range(len(i)-1):
            a = i[k] - 1
            b = i[k+1] - 1
            trial += c[a][b]
        ans = min(ans,trial)
    print(ans)




if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, r = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(r):
        l[i] -= 1
    edge = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        edge[i-1].append((j-1, k))
        edge[j-1].append((i-1, k))

    # dijkstra
    from heapq import heapify, heappush, heappop

    distance = [[-1] * n for _ in range(n)]
    for start in range(n):
        todo = [(0, start)]
        heapify(todo)

        while len(todo) > 0:
            cost, node = heappop(todo)
            if distance[start][node] == -1:
                distance[start][node] = cost

                for i in edge[node]:
                    if distance[start][i[0]] == -1:
                        heappush(todo, (cost + i[1], i[0]))

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += distance[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m, r = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(r):
        l[i] -= 1
    edge = [[] for _ in range(n)]
    weight = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        edge[i].append(j)
        edge[j].append(i)
        weight[i].append(k)
        weight[j].append(k)

    # dijkstra
    from heapq import heapify, heappush, heappop

    distance = [[-1] * n for _ in range(n)]
    for start in range(n):
        todo = [(0, start)]
        heapify(todo)

        while len(todo) > 0:
            cost, node = heappop(todo)
            if distance[start][node] == -1:
                distance[start][node] = cost

                for i in range(len(edge[node])):
                    if distance[start][edge[node][i]] == -1:
                        heappush(todo, (cost + weight[node][i], edge[node][i]))

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += distance[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

# 8! = 40320

n, m, r = map(int, input().split())
l = list(map(int, input().split()))
for i in range(r):
    l[i] -= 1
edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(m):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)
    weight[i].append(k)
    weight[j].append(k)

# dijkstra
from heapq import heapify, heappush, heappop

distance = [[-1] * n for _ in range(n)]
for start in range(n):
    todo = [(0, start)]
    heapify(todo)

    while len(todo) > 0:
        cost, node = heappop(todo)
        if distance[start][node] == -1:
            distance[start][node] = cost

            for i in range(len(edge[node])):
                if distance[start][edge[node][i]] == -1:
                    heappush(todo, (cost + weight[node][i], edge[node][i]))

# full search
from itertools import permutations

answer = float('inf')
for i in permutations(l):
    ans = 0
    for j in range(r-1):
        ans += distance[i[j]][i[j+1]]
    if ans < answer:
        answer = ans

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
ABC = [[float('inf')]*(N+1) for _ in range(N+1)]
#条件のうち、重複経路は最短のみ残す
for _ in range(M):
    a,b,c = map(int,input().split())
    if ABC[a][b]>c:
        ABC[a][b]=c
        ABC[b][a]=c
#整理
road = [[] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if ABC[i][j] != float('inf'):
            road[i].append((j,ABC[i][j]))
#各頂点間の最小距離
dist = [[float('inf')]*(N+1) for _ in range(N+1)]
q=collections.deque([])
q.append(1)
while q:
    now = q.popleft()
    for goto,cost in road[now]:
        if dist[now][goto]>cost:
            dist[now][goto] = cost
            dist[goto][now] = cost
            q.append(goto)

rotate = itertools.permutations(range(1,N+1))
ans = float('inf')
for rot in rotate:
    tmp = 0
    rset = set(r)
    for i in range(len(rot)-1):
        if tmp == 0 and rot[i] not in rset:
            break
        tmp +=dist[rot[i]][rot[i+1]]
        rset.discard(rot[i])
        rset.discard(rot[i+1])
        if tmp>ans:
            break
        if len(rset) == 0:
            ans = min(ans,tmp)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

#Dijkstra
def Dijkstra(D,From,To,with_path=False):
    """Dijksta法を用いて,FromからToまでの距離を求める.

    D:辺の重みが全て非負の有向グラフ
    From:始点
    To:終点
    with_path:最短路も含めて出力するか?

    (出力の結果)
    with_path=True->(距離,最短経路の辿る際の前の頂点)
    with_path=False->距離
    """
    from copy import copy
    from heapq import heappush,heappop

    T={v:float("inf") for v in D.vertex}
    T[From]=0

    if with_path:
        Prev={v:None for v in D.vertex}

    Q=[(0,From)]

    Flag=False
    while Q:
        c,u=heappop(Q)

        if u==To:
            Flag=True
            break

        if T[u]<c:
            continue

        for v in D.adjacent_out[u]:
            if T[v]>T[u]+D.adjacent_out[u][v]:
                T[v]=T[u]+D.adjacent_out[u][v]
                heappush(Q,(T[v],v))

                if with_path:
                    Prev[v]=u

    if not Flag:
        if with_path:
            return (float("inf"),None)
        else:
            return float("inf")

    if with_path:
        path=[To]
        u=To
        while (Prev[u]!=None):
            u=Prev[u]
            path.append(u)
        return (T[To],path[::-1])
    else:
        return T[To]
#================================================
from itertools import permutations
N,M,R=map(int,input().split())
Y=list(map(int,input().split()))
D=Digraph(list(range(1,N+1)))
for _ in range(M):
    a,b,c=map(int,input().split())
    D.add_edge(a,b,c)
    D.add_edge(b,a,c)

Z=float("inf")
for P in permutations(Y):
    X=0
    for i in range(R-1):
        X+=Dijkstra(D,P[i],P[i+1])
    Z=min(Z,X)
print(Z)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M, R = NMI()
    targets = NLI()
    targets = [t-1 for t in targets]
    dist = [[10**9] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = NMI()
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    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 case in permutations(targets, R):
        now = case[0]
        cost = 0
        for goto in case[1:]:
            cost += dist[now][goto]
            now = goto
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, R = map(int, input().split())
r = list(map(int, input().split()))

dis = [[float("inf") for i in range(n)] for j in range(n)]
for i in range(n):
    dis[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c

def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return dis

data = warshall_floyd(dis)
ans = float("inf")
for i in itertools.permutations(r, R):
    num = 0
    for j in range(R - 1):
        num += data[i[j] - 1][i[j + 1] - 1]
    ans = min(ans, num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[min(a-1,b-1), max(b-1,a-1)] = c 
del a, b, c, K

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0

def dfs(v, r, passed):
    global graph, dist
    passed.add(v)
    for nv in graph[v]:
        dist[r][nv] = dist[nv][r] =  min(dist[r][nv], dist[r][v] + cost[min(v,nv),max(v,nv)])
        if not nv in passed:
            dfs(nv, r, passed)
    passed.remove(v)
    return 0

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

passed = set()
for r in R:
    dfs(r, r, passed)
ans = min([mindist(r, R) for r in R])
print(ans)