fork download
copy 
  1. INF = 100000000000000
  2.  
  3. pickup = {}
  4. dest = {}
  5. trace = {}
  6. dp = {}
  7.  
  8. def calc(a, b):
  9. 	return abs(a[0] - b[0]) + abs(a[1] - b[1])
  10.  
  11. def solve(curPos, completed, ongoing):
  12. 	if len(completed) == N and len(ongoing) == 0:
  13. 		return 0
  14. 	curState = (curPos, frozenset(completed), frozenset(ongoing))	
  15.  
  16. 	if curState in dp.keys():
  17. 		return dp[curState]
  18.  
  19. 	minVal = INF
  20. 	for i in pickup.keys():
  21. 		if i in completed: continue
  22. 		newOngoing = ongoing.copy()
  23. 		newCompleted = completed.copy()
  24.  
  25. 		if i in ongoing:
  26. 			newOngoing.remove(i)
  27. 			newCompleted.add(i)
  28. 			val = calc(curPos, dest[i]) + solve(dest[i], newCompleted, newOngoing)
  29. 			if val < minVal:
  30. 				minVal = val
  31. 				trace[curState] = \
  32. 					("drop " + str(i), (dest[i], newCompleted, newOngoing))
  33. 		elif len(ongoing) < maxCustomers:
  34. 			newOngoing.add(i)
  35. 			val = calc(curPos, pickup[i]) + solve(pickup[i], newCompleted, newOngoing)
  36. 			if val < minVal:
  37. 				minVal = val
  38. 				trace[curState] = \
  39. 					("pickup " + str(i), (pickup[i], newCompleted, newOngoing))
  40.  
  41. 	dp[curState] = minVal
  42. 	return minVal
  43.  
  44. def path(state):
  45. 	stateVar = (state[0], frozenset(state[1]), frozenset(state[2]))
  46. 	if stateVar not in trace.keys():
  47. 		return
  48. 	print (trace[stateVar][0])
  49. 	if trace[stateVar][1] != None: 
  50. 		return path(trace[stateVar][1])
  51.  
  52. maxCustomers = int(input())
  53. rstr = input().split(",")
  54. start = (int(rstr[0]), int(rstr[1]))
  55. N = int(input())
  56. for i in range(N):
  57. 	line = input().split(",")
  58. 	pickup[int(line[0])] = (int(line[1]), int(line[2]))
  59. 	dest[int(line[0])] = (int(line[3]), int(line[4]))
  60.  
  61. print("Total distance travelled: ", solve(start, set(), set()))
  62. path((start, set(), set()))
  63.  
  64.  
Success #stdin #stdout 0.17s 28048KB
comments (?)
stdin
copy 
6
148,128
7
1,45,199,178,69
2,54,87,26,83
3,197,147,135,93
4,12,49,61,66
5,91,8,55,73
6,88,42,15,9
7,184,144,31,34
stdout
copy 
Total distance travelled:  929
pickup 7
pickup 3
pickup 1
pickup 2
pickup 6
pickup 5
drop 6
drop 7
pickup 4
drop 2
drop 5
drop 4
drop 3
drop 1
https://ideone.com/lKUql9
language:
Python 3 (python  3.9.5)
created:
5 years 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!