leetcode刷题笔记-Dijkstra's algorithm

 787. Cheapest Flights Within K Stops

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 fights, 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.

class Solution(object):
    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
        """
        prices = collections.defaultdict(dict)
        
        for a, b, p in flights:
            prices[a][b] = p
        
        heap = [(0, src, K+1)]
        while heap:
            price, curPlace, steps = heapq.heappop(heap)
            if curPlace == dst:
                return price
            
            if steps > 0:
                for arr in prices[curPlace]:
                    heapq.heappush(heap, (price+prices[curPlace][arr], arr, steps-1))
        return -1

 

743. Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

第一次尝试，题目理解错了。原来题目的意思是 点1传到2 用时间1， 1传给3用时间1， 那么1传给2和3 总共用时也是1，我理解成是2.

错误理解的代码：虽然理解错了做错了但是加深了我对DFS的运用理解。

class Solution(object):
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        # K in network is K-1
        network = [[0] * N for i in xrange(N)]
 
        for u, v, w in times:
            network[u - 1][v - 1] = w
 
        # find a DFS start position
        col = -1
        for i in network[K - 1]:
            if i != 0:
                col = i
 
        if col == -1:
            return -1
 
        res = []
 
        def dfs(network, row, col, res):
            if row < 0 or col < 0 or row > N - 1 or col > N - 1 or network[row][col] == '#':
                return
            if network[row][col] == 0 and row != col:
                return
            res.append(network[row][col])
            network[row][col] = '#'
 
            for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                dfs(network, row + i, col + j, res)
 
        dfs(network, K-1, col, res)
        print network
 
        check = []
        # check network
        for i in xrange(N):
            for j in xrange(N):
                if network[i][j] == '#':
                    check.append(j)
        for i in xrange(N-1):
            if i not in set(check):
                return -1
 
        return sum(res)
 
 
s = Solution()
print s.networkDelayTime([[2,1,1], [2,3,1], [3,4,1]], 4, 2)

看不懂答案，直接参考上面那一题自己写吧，代码不够简洁。

class Solution(object):
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        # K in network is K-1
        network = collections.defaultdict(dict)

        for u, v, w in times:
            network[u][v] = w

        time, curPlace = 0, K
        heap = [(time, curPlace)]

        # K-1
        unvisited = range(N)
        total = 0
        while unvisited:
            if not heap:
                return -1
            
            time, curPlace = heapq.heappop(heap)
            if curPlace - 1 in unvisited:
                unvisited.remove(curPlace - 1)
                total = max(total, time)
            else:
                continue
                
            if not unvisited: break
                
            for node in network[curPlace]:
                heapq.heappush(heap, (time + network[curPlace][node], node))
        return total