SHARE
TWEET

Untitled

a guest May 19th, 2019 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python3
  2. import sys
  3. from utils import *
  4. from collections import defaultdict
  5. from heapq import *
  6.  
  7. file = open(sys.argv[1], "r")
  8.  
  9. line = [int(x) for x in file.readline().split()]
  10. n = line[0]  # vertices
  11. m = line[1]  # edges
  12.  
  13. position_of_extra_node = n
  14.  
  15. n = n + 1  # extra S node
  16.  
  17. edges = [[] for i in range(n)]
  18. edge_costs = [[0 for j in range(n)] for i in range(n)]
  19. overwritten_at = [0] * n
  20. vertex_costs = [float("inf")] * n
  21.  
  22. for i in range(0, m):
  23.     line = [int(x) for x in file.readline().split()]
  24.     edges[line[0]].append(line[1])
  25.     edges[line[1]].append(line[0])
  26.  
  27.     edge_costs[line[0]][line[1]] = line[2]
  28.     edge_costs[line[1]][line[0]] = line[2]
  29.  
  30. #print(edges)
  31. #print("costs")
  32. #print(edge_costs)
  33.  
  34. is_terminals = [False] * n
  35. first_terminal = -1
  36. number_of_terminals = 0
  37.  
  38. terminals = []
  39.  
  40. for x in file.readline().split():
  41.     if first_terminal == -1:
  42.         first_terminal = int(x)
  43.  
  44.     terminals.append(int(x))
  45.     is_terminals[int(x)] = True
  46.     number_of_terminals = number_of_terminals + 1
  47.  
  48. file.close()
  49.  
  50. #  first 0 edge
  51. edges[position_of_extra_node].append(first_terminal)
  52. edges[first_terminal].append(position_of_extra_node)
  53. vertex_costs[position_of_extra_node] = 0
  54. overwritten_at[position_of_extra_node] = 1
  55.  
  56.  
  57.  
  58. #print("the source")
  59. #print(position_of_extra_node)
  60.  
  61. previous = [0] * n
  62.  
  63.  
  64. def backtrack_path_and_assign_zero(node):
  65.     #print("==== === BACKTRACKING")
  66.     #print(previous)
  67.  
  68.     if node == first_terminal:
  69.         vertex_costs[position_of_extra_node] = 0
  70.         vertex_costs[node] = 0
  71.         return
  72.  
  73.     while vertex_costs[node] != 0:
  74.         #print("Add EDGE from: ")
  75.         #        print(node)
  76.  
  77.         vertex_costs[node] = 0
  78.         edges[node].append(position_of_extra_node)
  79.         edges[position_of_extra_node].append(node)
  80.  
  81.         node = previous[node]
  82.  
  83.  
  84. def _print(node, cost, queue):
  85.     print("====== NEXT ===== ")
  86.     print("Node: ")
  87.     print(node)
  88.     print("Of Cost:")
  89.     print(cost)
  90.     print("Remaining in Q:")
  91.     print(len(queue))
  92.  
  93.  
  94. def _print1(node, visited, considered_cost):
  95.     print("- Visited:")
  96.     print(visited[node])
  97.     print("- New Cost:")
  98.     print(considered_cost)
  99.     print("_ Old Cost:")
  100.     print(vertex_costs[node])
  101.  
  102.  
  103. def dijkstra(run):
  104.     queue = []
  105.  
  106.     visited = [False] * n
  107.     visited[position_of_extra_node] = True
  108.  
  109.     for x in edges[position_of_extra_node]:
  110.         heappush(queue, (0, x))
  111.  
  112.     while len(queue) != 0:
  113.         (cost, node) = heappop(queue)
  114.  
  115.         #        _print(node, cost, queue)  # debug
  116.  
  117.         if is_terminals[node] and vertex_costs[node] != 0:
  118. #            print("==== TERMINATING")
  119.             backtrack_path_and_assign_zero(node)
  120.             return
  121.  
  122.         if visited[node]:
  123. #            print("=CANT HELP HERE")
  124.             continue
  125.  
  126.         if cost > vertex_costs[node]:
  127.             continue
  128.  
  129.         visited[node] = True
  130.  
  131. #        print("== NEIGHBORROWS:")
  132.         for x in edges[node]:
  133. #            print("Node: ")
  134. #            print(x)
  135.  
  136.             considered_cost = edge_costs[node][x] + vertex_costs[node]
  137.  
  138. #            _print1(x, visited, considered_cost)
  139.  
  140.             if considered_cost < vertex_costs[x]:
  141.  
  142.  #               print("-- ADD IT!")
  143.                 overwritten_at[x] = run
  144.                 vertex_costs[x] = considered_cost
  145.                 previous[x] = node
  146.  
  147.                 heappush(queue, (vertex_costs[x], x))
  148.  
  149.             elif not visited[x] and overwritten_at[x] < run and vertex_costs[x] == considered_cost:
  150.  
  151.   #              print("-- ADD IT anyway!")
  152.                 heappush(queue, (vertex_costs[x], x))
  153.  
  154.  
  155. for i in range(number_of_terminals):
  156. #    print("================= NEW ROUND")
  157.     # adjusted_dijkstra()
  158.  
  159.     dijkstra(i + 1)
  160.  
  161. result_edges = []
  162.  
  163. def backtrack_result(node):
  164.  
  165.     cost = 0
  166.  
  167.     while edge_costs[node][previous[node]] != 0:
  168.         result_edges.append((node, previous[node]))
  169.  
  170.         cost = cost + edge_costs[node][previous[node]]
  171.  
  172.         edge_costs[node][previous[node]] = 0
  173.         edge_costs[previous[node]][node] = 0
  174.  
  175.         node = previous[node]
  176.  
  177.     return cost
  178.  
  179.  
  180. result_cost = 0
  181. for x in terminals:
  182.     result_cost = result_cost + backtrack_result(x)
  183.  
  184. #print("===== THE RESULT =====")
  185. #print(result_cost)
  186.  
  187. #print("===== THE EDGES  =====")
  188. #for x in result_edges:
  189. #    print(x)
  190.  
  191.  
  192.  
  193.  
  194. # print("last terminal ")
  195. # print(last_terminal)
  196. # print(terminals)
  197. file1 = open(sys.argv[2], "w")
  198. file1.write(str(result_cost))
  199. file1.write("\n")
  200.  
  201. for i in result_edges:
  202.     file1.write(str(i[0]))
  203.     file1.write(" ")
  204.     file1.write(str(i[1]))
  205.     file1.write("\n")
  206.  
  207. file1.close()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top