# There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.
#
# Now given all the cities and flights, together with starting city src and the destination dst, your task is to find
#  the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
#
# Example 1:
# Input:
# n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
# src = 0, dst = 2, k = 1
# Output: 200
# Explanation:
# The graph looks like this:
#
#
# The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
# Example 2:
# Input:
# n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
# src = 0, dst = 2, k = 0
# Output: 500
# Explanation:
# The graph looks like this:
#
#
# The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
# Note:
#
# The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
# The size of flights will be in range [0, n * (n - 1) / 2].
# The format of each flight will be (src, dst, price).
# The price of each flight will be in the range [1, 10000].
# k is in the range of [0, n - 1].
# There will not be any duplicated flights or self cycles.
import collections
import heapq


class Solution(object):
    def findCheapestPrice_bfs(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        costs, que = [[float('inf')] * n for _ in xrange(n)], collections.deque()

        for f in flights:
            costs[f[0]][f[1]] = f[2]

        minCost, visited = float('inf'), set()
        visited.add(src)
        # append (node, cost) tuple
        que.append((src, 0))

        while que:
            m = len(que)
            for i in xrange(m):
                s, c = que.popleft()
                for d in xrange(n):
                    if d not in visited and costs[s][d] < float('inf'):
                        nC = c + costs[s][d]
                        # pruning
                        if nC > minCost:
                            continue
                        if d == dst:
                            minCost = min(minCost, nC)
                        if K == 0:
                            continue
                        que.append((d, nC))
            K -= 1
        return minCost if minCost < float('inf') else -1

    def findCheapestPrice_TLE(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """

        def dfs(costs, source, k, cost, memo):
            if k < 0:
                return
            if k >= 0 and source == dst:
                self.minCost = min(self.minCost, cost)
                return
            for i in xrange(n):
                if costs[source][i] < float('inf'):
                    t = cost + costs[source][i]
                    # pruning
                    if t > self.minCost:
                        continue  # bugfixed
                    dfs(costs, i, k - 1, t)
            return

        costs = [[float('inf')] * n for _ in xrange(n)]
        for f in flights:
            costs[f[0]][f[1]] = f[2]

        self.minCost = float('inf')
        dfs(costs, src, K + 1, 0)

        return self.minCost if self.minCost < float('inf') else -1

    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """

        def dfs(costs, source, k, cost, visited):
            if k < 0:
                return
            if k >= 0 and source == dst:
                self.minCost = cost
                return
            for i in xrange(n):
                if i not in visited and costs[source][i] < float('inf'):
                    t = cost + costs[source][i]
                    # pruning
                    if t > self.minCost:
                        continue  # bugfixed
                    visited.add(i)
                    dfs(costs, i, k - 1, t, visited)
                    visited.discard(i)
            return

        costs, visited = [[float('inf')] * n for _ in xrange(n)], set()
        visited.add(src)
        for f in flights:
            costs[f[0]][f[1]] = f[2]

        self.minCost = float('inf')
        dfs(costs, src, K + 1, 0, visited)

        return self.minCost if self.minCost < float('inf') else -1

    # time complexity : O(E * K), E is the stop numbers of flights
    # space: O(N * K)
    def findCheapestPrice_dp(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """

        # dp[i][j] change airport i times then reach j airport , the min cost
        # stop K times, means when reached dst, we change airport K+1 times
        # so dp[K+1][dst] is the final solution
        dp = [[float('inf')] * n for _ in xrange(K + 2)]
        # since it is start from source, so the cost is 0
        dp[0][src] = 0

        # stop K times means we need to change airport K+1 times, take dfs solution as references
        for i in xrange(1, K + 2):
            dp[i][src] = 0
            for f in flights:
                # i times to f[1] means need to choose min from  [i-1 times to f[0] then from f[0] to f[1]]
                dp[i][f[1]] = min(dp[i][f[1]], dp[i - 1][f[0]] + f[2])

        return dp[K + 1][dst] if dp[K + 1][dst] < float('inf') else -1

    # 2 dim -> 1 dim
    # time complexity : O(E * K), E is the stop numbers of flights
    # space: O(N)
    def findCheapestPrice_dp2(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        dp = [float('inf')] * n
        dp[src] = 0
        for i in xrange(1, K + 2):
            tmp = [float('inf')] * n
            tmp[src] = 0
            for f in flights:
                tmp[f[1]] = min(tmp[f[1]], dp[f[0]] + f[2])

            dp = tmp

        return dp[dst] if dp[dst] < float('inf') else -1

    # dijkastra
    def findCheapestPrice_di1(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        # knowledge nested dict
        f = collections.defaultdict(dict)

        for a, b, c in flights:
            # knowledge compared with 2-dim list, this saves spaces
            f[a][b] = c

        pq = [(0, src, K + 1)]

        while pq:
            p, i, k = heapq.heappop(pq)
            if i == dst:
                return p
            if k > 0:
                for j in f[i]:
                    heapq.heappush(pq, (p + f[i][j], j, k - 1))
        return -1

    # dijkastra
    def findCheapestPrice_di2(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        # knowledge nested dict
        f = collections.defaultdict(dict)
        record = {}

        for a, b, c in flights:
            # knowledge compared with 2-dim list, this saves spaces
            f[a][b] = c

        pq = [(0, src, K + 1)]

        while pq:
            p, i, k = heapq.heappop(pq)
            # prunning, so good
            if k < 0 or p > record.get((k, i), float('inf')):
                continue
            if i == dst:
                return p
            for j in f[i]:
                # knowledge how to use pairs as key
                if p + f[i][j] < record.get((k - 1, j), float('inf')):
                    heapq.heappush(pq, (p + f[i][j], j, k - 1))
                    record[k - 1, j] = p + f[i][j]
        return -1

if __name__ == '__main__':
    print Solution().findCheapestPrice_bfs(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)
    print Solution().findCheapestPrice_di2(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)
    print Solution().findCheapestPrice_bfs(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0)
    print Solution().findCheapestPrice_di2(4, [[0, 1, 1], [0, 2, 5], [1, 2, 1], [2, 3, 1]], 0, 3, 1)

    # Finished in 1624 - dfs
    # ms
    # 1502
    # Finished in 124 - bfs
    # ms
    # 1502
    # Finished in 52 - dp 1
    # ms
    # 1502
    # Finished in 44 - dp 2
    # ms
    # 1502
    # Finished in 44 - heap 1
    # ms
    # 1502
    # Finished in 28 - heap 2
    # ms
    # 1502
