推 JKWP: 怎麼不寫今天的 01/31 01:27
好幾天前的
好久沒用dijkstra
都忘記可以early return
能過但很慢
還傻傻的在那邊記edge index
好像根本不用
對ㄚ
def minCost(self, n: int, edges: List[List[int]]) -> int:
g = defaultdict(list)
dist = {i:10**10 for i in range(n)}
dist[0] = 0
for idx, e in enumerate(edges):
u, v, w = e[0], e[1], e[2]
g[u].append((v, w, idx)) # node, weight, edge_idx
g[v].append((u, 2*w, idx))
pq = [(0, 0)] # (dist, node_idx)
visited_edge = set()
while pq:
cur_dist, cur_n = heapq.heappop(pq)
if cur_dist>dist[cur_n]:
continue
for next_n, w, e_idx in g[cur_n]:
if e_idx in visited_edge:
continue
if cur_dist+w < dist[next_n]:
dist[next_n] = cur_dist+w
heappush(pq, (dist[next_n], next_n))
visited_edge.add(e_idx)
return -1 if dist[n-1]==10**10 else dist[n-1]
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1769793984.A.6F6.html