The Ticket to Ride Problem

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)

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.

The Ticket to Ride Problem