Re: [闲聊] 每日leetcode

楼主: dont   2024-07-28 14:49:38
2045. Second Minimum Time to Reach Destination
## 思路
先建Graph, 因为边的权重都一样所以直接用BFS就好了
找第二小的 所以每个点最多走两次 (ex. 1-2, 1-2-1-2)
用两个dict纪录两次遇到的时间、判断要不要加进queue
## Code
```python
class Solution:
def secondMinimum(self, n: int, edges: List[List[int]], time: int,
change: int) -> int:
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen1 = defaultdict(int)
seen2 = defaultdict(int)
seen1[1] = 0
queue = deque([(1)])
has_meet_smallest = False
curr_time = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node == n:
if has_meet_smallest:
return curr_time
has_meet_smallest = True
for next_node in graph[node]:
if next_node not in seen1:
seen1[next_node] = curr_time
queue.append(next_node)
elif curr_time > seen1[next_node] and next_node not in
seen2:
seen2[next_node] = curr_time
queue.append(next_node)
if (curr_time // change) & 1:
curr_time = (curr_time // change + 1) * change
curr_time += time
return -1
```
作者: Smallsh (Smallsh)   2024-07-28 14:50:00
大师
作者: sustainer123 (caster)   2024-07-28 15:31:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com