姆咪不太会
第一个是最后算解答那边搞了好久 好白痴
第二个是 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