Usage: ``python get_cheapest_shortest_path.py 'city1' 'city2'

get_cheapest_shortest_path.py

from collections import defaultdict
import sys

time = {
    'Oslo': [
        {'London': 45},
        {'Dubai': 420},
        {'Melbourne': 700},
    ],
    'London': [
        {'Dubai': 480},
        {'Melbourne': 740},
    ],
    'Dubai': [
        {'Melbourne': 460},
    ],
}

cost = {
    'Oslo': [
        {'London': 70},
        {'Dubai': 300},
        {'Melbourne': 1000},
    ],
    'London': [
        {'Dubai': 180},
        {'Melbourne': 950},
    ],
    'Dubai': [
        {'Melbourne': 230},
    ],
}

# Global parameters
best_cost = sys.maxint
best_time = sys.maxint
best_path = []

def convert_list_to_dict(list_of_obj, default_value = False):
    """This method converts list of objects to dict.

    :param list_of_obj:   A list of obj currently supporting 'dict' and 'str' types.
    :param default_value: Assigns a default value to each key entry.
    """
    new_dict = {}
    for item in list_of_obj:
        if isinstance(item, (dict,)):
            new_dict.update(item)
        elif isinstance(item, (str,)):
            new_dict.update({item: default_value})

    return new_dict

class Edge:
    """ Stores the properties of an edge in a weighted graph.

    Typical usage:

        new_edge = Edge(source, destination, time, code)
    """
    def __init__(self, source, destination, time, cost):
        self.source = source
        self.destination = destination
        self.time = time
        self.cost = cost

class Graph:
    """ Stores the properties of a graph.

    Typical usage:

        g = Graph()
        g.load(time_dict, cost_dict)
        print g.graph
        print g.vertices
    """

    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = []

    def addEdge(self, source, destination, time, cost):
        """ Adds an edge between vertices and stores their ``time`` and ``cost`` weights.

        :param source:      The starting point.
        :param destination: The ending point.
        :param time:        Time weight.
        :param cost:        Cost weight.

        It is assumed that it is a directed weighted graph.
        """
        self.graph[source].append(Edge(source, destination, time, cost))

    def load(self, time_dict, cost_dict):
        """ Loads ``time_dict`` and ``cost_dict`` to form a graph.

        :param time_dict: A dict of list connecting vertices as a dict with time weight as value.
        :param cost_dict: A dict of list connecting vertices as a dict with cost weight as value.
        """
        for source in time_dict.keys():
            new_time_dict = convert_list_to_dict(time_dict[source])
            new_cost_dict = convert_list_to_dict(cost_dict[source])
            for destination in new_time_dict.keys():
                self.addEdge(source, destination, new_time_dict[destination], new_cost_dict[destination])
                if destination not in self.vertices:
                    self.vertices.append(destination)
            if source not in self.vertices:
                self.vertices.append(source)

def find_cheapest_shortest_path(graph, source, destination, visited, path = [], time = 0, cost = 0, parent_node = True):
    """ Recursively finds the cheapest and shortest path under the condition given in the problem statement.

    :param graph:       A defaultdict() containing a list of edges.
    :param source:      The city from which the journey is staring.
    :param destination: The city where the journey ends.
    :param visited:     A dict of vertices with default_value as 'False' to check if the vertice is visited or not.
    :param path:        A list of cities covered in the journey.
    :param time:        Time taken to cover the path.
    :param cost:        Cost of covering the path.
    :parent_node:       To check if it is the starting point of the journey or not.

    Typical usage:

        find_cheapest_shortest_path(graph, source, destination, visited)

    This updates the global parameters, ``best_path``, ``best_time`` and ``best_cost``.
    """
    visited[source] = True
    flag = True

    global best_time
    global best_cost
    global best_path

    if source==destination:
        if best_cost >= cost or ((best_time - time) >= 120 and (best_cost - cost) <=100): # Condition in the problem statement
            best_cost = cost
            best_time = time
            best_path = path + [destination]
    else:
        if source in graph.keys():
            path.append(source)
            for edge in graph[source]:
                if visited[edge.destination] == False:
                    if parent_node == True:
                        time = 0
                        cost = 0
                    time+=edge.time
                    cost+=edge.cost
                    if cost >= best_cost + 100 and time >= best_time - 120: # Condition in the problem statement
                        flag = False
                    if flag == True:
                        find_cheapest_shortest_path(graph, edge.destination, destination, visited, path, time, cost, False)

    visited[source] = False

if __name__ == '__main__':

    city1 = sys.argv[1]
    city2 = sys.argv[2]

    g = Graph()
    g.load(time, cost)
    visited = convert_list_to_dict(g.vertices)
    find_cheapest_shortest_path(g.graph, city1, city2, visited)

    if best_path == []:
        print "No path found!!!"
    else:
        for i in range(len(best_path)-1):
            source = best_path[i]
            destination = best_path[i+1]
            for edge in g.graph[source]:
                if destination == edge.destination:
                    print "%s --> %s, %d h %02d mins, %d$" % (source, destination, edge.time/60, edge.time%60, edge.cost)
                    break
        print
        print "%d h %02d mins, %d$" % (best_time/60, best_time%60, best_cost)

I have assumed that it is a sparse directed weighted graph. So I have used an adjacency list instead of an adjacency matrix.
Example usage: python get_cheapest_shortest_path.py 'London' 'Melbourne'
Result:
London --> Dubai, 8 h 00 mins, 180$
Dubai --> Melbourne, 7 h 40 mins, 230$

15 h 40 mins, 410$