姆咪不太會
第一個是最後算解答那邊搞了好久 好白癡
第二個是 BFS的剪枝 我不知道為啥這樣不會TLE 我原本寫的會==
改天再來想想
def secondMinimum(self, n: int, edges: List[List[int]], time: int, change:
int) -> int:
g = defaultdict(list)
for e in edges:
g[e[0]].append(e[1])
g[e[1]].append(e[0])
q = deque()
visited = set()
q.append((1, 0))
dis = [10**9 for _ in range(n+1)]
dis2 = [10**9 for _ in range(n+1)]
while q:
node, dis_cur = q.pop()
for neighbor in g[node]:
new_dis = dis_cur+1
if new_dis < dis[neighbor]:
dis2[neighbor], dis[neighbor] = dis[neighbor], new_dis
q.appendleft((neighbor, new_dis))
elif new_dis > dis[neighbor] and new_dis < dis2[neighbor]:
dis2[neighbor] = new_dis
q.appendleft((neighbor, new_dis))
print(dis[n], dis2[n])
ans = 0
for i in range(dis2[n]):
if (ans-change) >= 0 and 0 <= (ans-change) % (change*2) < change:
ans = ((ans) // (change*2) + 1) * (change*2) + time
else:
ans += time
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722178491.A.78C.html
※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 07/28/2024 22:57:52