fork download
copy 
  1. import sys
  2. import heapq
  3. from itertools import permutations
  4.  
  5. def main():
  6.     input = sys.stdin.read().split()
  7.     ptr = 0
  8.     n, m = int(input[ptr]), int(input[ptr+1])
  9.     ptr += 2
  10.  
  11.     adj = [[] for _ in range(n+1)]
  12.     for _ in range(m):
  13.         a = int(input[ptr])
  14.         b = int(input[ptr+1])
  15.         t = int(input[ptr+2])
  16.         adj[a].append((b, t))
  17.         adj[b].append((a, t))
  18.         ptr += 3
  19.  
  20.     dragon_balls = list(map(int, input[ptr:ptr+7]))
  21.     ptr += 7
  22.     targets = list(set(dragon_balls))
  23.  
  24.     def dijkstra(start):
  25.         dist = [float('inf')] * (n + 1)
  26.         dist[start] = 0
  27.         heap = [(0, start)]
  28.         heapq.heapify(heap)
  29.         while heap:
  30.             d, u = heapq.heappop(heap)
  31.             if d > dist[u]:
  32.                 continue
  33.             for v, w in adj[u]:
  34.                 if dist[v] > d + w:
  35.                     dist[v] = d + w
  36.                     heapq.heappush(heap, (dist[v], v))
  37.         return dist
  38.  
  39.     # Compute distances from city 1
  40.     dist_1 = dijkstra(1)
  41.  
  42.     # Check if all targets are reachable from 1
  43.     for city in targets:
  44.         if dist_1[city] == float('inf'):
  45.             print(-1)
  46.             return
  47.  
  48.     # Precompute distances between all pairs of targets
  49.     dists = {}
  50.     # Check if 1 is among the targets to use dist_1
  51.     if 1 in targets:
  52.         dists[1] = dist_1
  53.  
  54.     for city in targets:
  55.         if city != 1:
  56.             dists[city] = dijkstra(city)
  57.  
  58.     # Now calculate all permutations and find the minimal cost
  59.     min_cost = float('inf')
  60.     for perm in permutations(targets):
  61.         current_cost = 0
  62.         current_cost += dist_1[perm[0]]
  63.         valid = True
  64.         for i in range(len(perm) - 1):
  65.             u = perm[i]
  66.             v = perm[i+1]
  67.             if dists[u][v] == float('inf'):
  68.                 valid = False
  69.                 break
  70.             current_cost += dists[u][v]
  71.             if current_cost >= min_cost:
  72.                 break  # Early exit if current exceeds current minimum
  73.         if valid and current_cost < min_cost:
  74.             min_cost = current_cost
  75.  
  76.     if min_cost == float('inf'):
  77.         print(-1)
  78.     else:
  79.         print(min_cost)
  80.  
  81. if __name__ == '__main__':
  82.     main()
Success #stdin #stdout 0.03s 7508KB
comments (?)
stdin
copy 
10 9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 2 3 4 5 6 7
stdout
copy 
6
https://ideone.com/a6uonD
language:
Python (cpython 2.7.16)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!