The Ticket to Ride Problem as follows: (actually is a mixed shortest path problem)
Source: https://www.hackerrank.com/challenges/ticket-to-ride/problem
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game.
There are n cities on the map and n-1 road plans. Each road plan consists of the following:
- Two cities which can be directly connected by a road.
- The length of the proposed road.
The entire road plan is designed in such a way that if one builds all the roads, it will be possible to travel between any pair of cities.
A ticket enables you to travel between two different cities. There are m tickets, and each ticket has a cost associated with it. A ticket is considered to be useful if there is a path between those cities.
Simon wants to choose two cities, u and v, and build a minimal number of roads so that they form a simple path between them. Let S_t be the sum of costs of all useful tickets and be the sum of lengths of all the roads Simon builds. The profit for pair (u,v) is defined as S_t - S_r. Note that and v are not necessarily unique and may be the same cities.
Given road plans and ticket prices, help Simon by printing the value of his maximum possible profit on a new line.
Input Format
The first line contains single positive integer, n, denoting the number of cities.
Each of the n-1 subsequent lines contains three space-separated integers describing the respective values of u, v, and l for a road plan, where 1<=u, v<=n, and u!=v. Here, v and u are two cities that the road plan proposes to connect and is the length of the proposed road.
The next line contains a single positive integer, m, denoting the number of tickets.
Each of the m subsequent lines contains three space-separated integers describing the respective values of u, v, and c for a ticket from city u to city v (where c is the cost of the ticket).
Output Format
Print a single integer denoting the the maximum profit Simon can make.
Thoughts
- In the problem, the road build cost is actually the length, hence we are to find the shortest path between source node and sink node. Hence we can use dijkstra algorithm. For more details about dijkstra algorithm you can refer to my another article
- Boundary: Be careful! Those ticket are not to be unique, hence if you encounter ticket (1,4,10) and (1,4,6), by the rule of this problem you should add them up to be (1,4,16)
- Data Structure: In this problem where you need to store a hell lot of information, one of the best way is to use a dictionary. In my method I prefer to 'from collections import defaultdict(list)' in which I initialize a dict which values can be appended by 'dict[key].append(new_value)'.
- Divide and Conquor: It'd be much better if you write and test functions one by one and eventually combine them together to perform the complicated task.
Code
Part of the Dijkstra algorithm is debugged and modified from here.
First is a one-time run version. You can copy and paste to any .py file and run on any IDE.
Result should be 13 and for the reason check here in the example.
# We first load the Dijkstra algorithms from collections import defaultdict class Graph: def __init__(self): self.nodes = set() # set object self.edges = defaultdict(list) self.distances = {} def add_nodes(self, value): for i in value: self.nodes.add(i) # add element into set def add_edge(self, from_node, to_node, distance): self.edges[from_node].append(to_node) self.edges[to_node].append(from_node) # dict to neighbour nodes self.distances[(from_node, to_node)] = distance # dict for distance self.distances[(to_node, from_node)] = distance # ------------------------------------- def dijkstra(graph, initial): visited = {initial: 0} path = {} nodes = set(graph.nodes) while nodes: min_node = None for node in nodes: if node in visited: if min_node is None: min_node = node elif visited[node] < visited[min_node]: min_node = node if min_node is None: break nodes.remove(min_node) current_weight = visited[min_node] for edge in graph.edges[min_node]: weight = current_weight + graph.distances[(min_node, edge)] if edge not in visited or weight < visited[edge]: visited[edge] = weight path[edge] = min_node return visited, path # Now is the body part n_node = 7 g = Graph() g.add_nodes([i+1 for i in range(n_node)]) # -- n_lst = [[1,2,1],[1,3,1],[1,4,4],[4,5,1],[4,6,1],[4,7,1]] for i in range(n_node-1): start, end, cost = n_lst[i] g.add_edge(start, end, cost) # know from setting that the network is a tree: node = arc + 1 # 可知每两个点之间一定可达 # --------- print "nodes:", g.nodes print "edges:", g.edges print "distances: ", g.distances # ---------- print "-" * 25 def createPath(path, source): dict_path = defaultdict(list) for node in path: # path = {node: predessesor} dict_path[node].append(node) while dict_path[node][-1] != source: dict_path[node].append(path[dict_path[node][-1]]) for node in dict_path: dict_path[node].reverse() return dict_path result_dict = defaultdict(list) for node in range(1, n_node+1): shortest_d, path = dijkstra(g, node) # source node as node result_dict[node].append(shortest_d) dict_path = createPath(path, node) result_dict[node].append(dict_path) # now we have result_dict that almost contain everything # dict: {node: [dict:{shortest path to all nodes}, dict:{list of path from source to node}]} ticket_n = 5 ticket_lst = [[5,7,3],[3,6,2],[3,4,10],[2,7,15],[1,6,7]] ticket_dict = {} for i in range(ticket_n): depart, dest, price = ticket_lst[i] if (depart, dest) in ticket_dict: # Careful! If two same ticket with different price if ticket_dict[(depart, dest)] != price: ticket_dict[(depart, dest)] += price else: ticket_dict[(depart, dest)] = price max_profit = 0 for start in range(1, n_node): for end in range(start+1, n_node+1): path_set = set(result_dict[start][1][end]) profit = sum([ticket_dict[key] for key in ticket_dict if set(key).issubset(path_set)]) - result_dict[start][0][end] # profit is counted as Tour price - Build cost if profit > max_profit: max_profit = profit print "Max profit is:" print max_profit print "=" * 25
Next I give a interactive version using which you can copy and paste the following input or handwrite into the code and check the output.
Input: (Output answer should be 42)
5 1 3 1 5 2 4 4 1 3 4 5 10 10 2 4 6 2 3 9 2 4 10 3 5 10 3 5 4 3 4 1 5 3 6 1 5 3 3 1 1 2 4 10
Now comes the python code.
# Enter your code here. Read input from STDIN. Print output to STDOUT from collections import defaultdict class Graph: def __init__(self): self.nodes = set() self.edges = defaultdict(list) self.distances = {} def add_nodes(self, value): for i in value: self.nodes.add(i) def add_edge(self, from_node, to_node, distance): self.edges[from_node].append(to_node) self.edges[to_node].append(from_node) self.distances[(from_node, to_node)] = distance self.distances[(to_node, from_node)] = distance def dijkstra(graph, initial): visited = {initial: 0} path = {} nodes = set(graph.nodes) while nodes: min_node = None for node in nodes: if node in visited: if min_node is None: min_node = node elif visited[node] < visited[min_node]: min_node = node if min_node is None: break nodes.remove(min_node) current_weight = visited[min_node] for edge in graph.edges[min_node]: weight = current_weight + graph.distances[(min_node, edge)] if edge not in visited or weight < visited[edge]: visited[edge] = weight path[edge] = min_node return visited, path n_node = int(raw_input().strip()) g = Graph() g.add_nodes([i + 1 for i in range(n_node)]) for i in range(n_node - 1): start, end, cost = map(int, raw_input().strip().split(" ")) g.add_edge(start, end, cost) # know from setting that network is tree: node = arc + 1 def createPath(path, source): dict_path = defaultdict(list) for node in path: dict_path[node].append(node) while dict_path[node][-1] != source: dict_path[node].append(path[dict_path[node][-1]]) for node in dict_path: dict_path[node].reverse() return dict_path result_dict = defaultdict(list) for node in range(1, n_node + 1): shortest_d, path = dijkstra(g, node) result_dict[node].append(shortest_d) dict_path = createPath(path, node) result_dict[node].append(dict_path) # now we have result_dict with all info ticket_n = int(raw_input().strip()) ticket_dict = {} for i in range(ticket_n): depart, dest, price = map(int, raw_input().strip().split(" ")) if (depart, dest) in ticket_dict: if ticket_dict[(depart, dest)] != price: ticket_dict[(depart, dest)] += price else: ticket_dict[(depart, dest)] = price max_profit = 0 for start in range(1, n_node): for end in range(start + 1, n_node + 1): path_set = set(result_dict[start][1][end]) profit = sum([ticket_dict[key] for key in ticket_dict if set(key).issubset(path_set)]) - result_dict[start][0][ end] # print "Pair: ", (start, end) # print "Distance:", result_dict[start][0][end] # print "List: ", [ticket_dict[key] for key in ticket_dict if set(key).issubset(path_set)] # print "Profit:", profit # profit = Ticket Price - Build Cost if profit > max_profit: max_profit = profit print max_profit
P.S. The above brutal code actually exceeds the time limit in the coding test = =, please share with me better ideas or solutions. Any suggestions and discussion will be very welcome.
Leave A Comment