2039.网络空闲的时刻
2039.网络空闲的时刻
题解
本题就是求最远的一个点最后接收到消息+1的时间的多少，并且发收消息走的都是最短路
那么本题的关键就是在求出最后一次发送消息的时间+来回路径长+1即可
那么最后一次发送消息怎么算呢，假设来回长是d，重发间隔为p，那么最后发送消息的时间就是公式(d-1)/p * p,为什么是d-1呢，因为在收到消息的那一刻，是不重发消息的
那么ans的公式就是(d-1)/p * p + d + 1，p是已知的，d通过最短路即可求出来
代码
func networkBecomesIdle(edges [][]int, patience []int) int { e := make([][]int, len(patience)) for _, edge := range edges { u, v := edge[0], edge[1] e[u] = append(e[u], v) e[v] = append(e[v], u) } dist := make([]int, len(patience)) for i := range dist { dist[i] = 0x3f3f3f3f } dist[0] = 0 vis := make([]int, len(patience)) queue := []int{0} for len(queue) > 0 { u := queue[0] queue = queue[1:] vis[u] = 0 for _, v := range e[u] { if dist[v] > dist[u]+1 { dist[v] = dist[u] + 1 if vis[v] == 0 { vis[v] = 1 queue = append(queue, v) } } } } ans := 0 for i := 1; i < len(patience); i++ { d, p := dist[i]*2, patience[i] ans = max(ans, (d-1)/p*p+d+1) } return ans } func max(i, j int) int { if i > j { return i } return j }
