本文共 2745 字，大约阅读时间需要 9 分钟。

为了解决这个问题，我们需要找到从起点到终点的最短路径，可以选择是否使用传送门一次。传送门可以看作是一个特殊的节点，可以在图中使用一次。我们需要计算两种情况：不使用传送门和使用传送门，然后比较这两种情况的最小代价。

方法思路

解决代码

import heapqdef main():    import sys    input = sys.stdin.read    data = input().split()    idx = 0    n = int(data[idx])    idx +=1    m = int(data[idx])    idx +=1    w = int(data[idx])    idx +=1    INF = float('inf')    a = [[INF]*(m+1) for _ in range(n+1)]    for i in range(1, n+1):        for j in range(1, m+1):            a[i][j] = int(data[idx])            idx +=1    d1 = [[INF]*(m+1) for _ in range(n+1)]    d2 = [[INF]*(m+1) for _ in range(n+1)]    dirs = [(0,1), (1,0), (0,-1), (-1,0)]    for i in range(1, n+1):        for j in range(1, m+1):            d1[i][j] = INF            d2[i][j] = INF    def dijkstra(start, n, m):        dist = [[INF]*(m+1) for _ in range(n+1)]        dist[start] = 0        heap = []        heapq.heappush(heap, (0, start))        while heap:            d, u = heapq.heappop(heap)            if d > dist[u]:                continue            for dx, dy in dirs:                v = u + dx                if v < 1 or v > n:                    continue                if a[u][v] + d < dist[v]:                    dist[v] = d + a[u][v]                    heapq.heappush(heap, (dist[v], v))        return dist    d1 = dijkstra(1, n, m)    d2 = dijkstra(n, n, m)    min_no_portal = d1[n][m]    min_portal_one = INF    for i in range(1, n+1):        for j in range(1, m+1):            if d1[i][j] >= INF or d2[i][j] >= INF:                continue            cost = d1[i][j] + d2[i][j]            if cost < min_portal_one:                min_portal_one = cost    min_portal_two = INF    for i in range(1, n+1):        for j in range(1, m+1):            if d1[i][j] >= INF or d2[j][i] >= INF:                continue            cost = d1[i][j] + a[i][j] + d2[j][i]            if cost < min_portal_two:                min_portal_two = cost    candidates = []    if min_portal_one != INF:        candidates.append(min_portal_one)    if min_portal_two != INF:        candidates.append(min_portal_two)    if min_no_portal != INF:        candidates.append(min_no_portal)    if not candidates:        print(-1)    else:        min_total = min(candidates)        if min_total > 1e17:            print(-1)        else:            print(min_total)if __name__ == '__main__':    main()

代码解释

转载地址：http://vadkz.baihongyu.com/