2662. 前往目標(biāo)的最小代價(jià)
請(qǐng)復(fù)習(xí)dij，屑娜庇！
class Solution(object):
def minimumCost(self, start, target, sr):
"""
:type start: List[int]
:type target: List[int]
:type specialRoads: List[List[int]]
:rtype: int
"""
n = len(sr)
sr2 = []
for i in range(n):
if abs(sr[i][0] - sr[i][2]) + abs(sr[i][1] - sr[i][3]) < sr[i][-1]:
continue
sr2.append(sr[i])
sr = sr2
mp = {}
for i in range(len(sr)):
mp[tuple(sr[i][:-1])] = sr[i][-1]
points = [tuple(start), tuple(target)]
for p in sr:
if (p[0], p[1]) not in points:
points.append((p[0], p[1]))
if (p[2], p[3]) not in points:
points.append((p[2], p[3]))
n = len(points)
inf = int(1e19)
dist = [[inf] * n for _ in range(n)]
for i in range(n):
for j in range(n):
x1, y1 = points[i]
x2, y2 = points[j]
if (x1, y1, x2, y2) in mp:
cost = mp[(x1, y1, x2, y2)]
dist[i][j] = min(dist[i][j], cost)
dist[i][j] = min(dist[i][j], abs(x1 - x2) + abs(y1 - y2))
# print(points)
# for r in dist:
# print(r)
d = [inf] * n
d[0] = 0
visit = set()
for i in range(1, n):
t = -1
for j in range(n):
if j not in visit and (t == -1 or d[j] < d[t]):
t = j
for j in range(n):
d[j] = min(d[j], d[t] + dist[t][j])
visit.add(t)
# print(d)
return d[1]
