2045.到达目的地的第二短时间

题解

求次短重点在于这一句else if dist[next][0] < cost && cost < dist[next][1]，而边没有权重，可以看作无向图，先把路径算作1即可

代码

package main

import (
	"math"
)

type pair struct {
          
   
	nextNode, step int
}

func secondMinimum(n int, edges [][]int, time int, change int) int {
          
   
	//双向图，graph存边
	graph := make([][]int, n+1)
	for _, e := range edges {
          
   
		x, y := e[0], e[1]
		graph[x] = append(graph[x], y)
		graph[y] = append(graph[y], x)
	}
	//dist[n][0]表示1到n的最短路径，dist[n][1]表示1到n的次短路径
	dist := make([][2]int, n+1)
	for i := 1; i <= n; i++ {
          
   
		dist[i] = [2]int{
          
   math.MaxInt32, math.MaxInt32}
	}
	queue := []pair{
          
   {
          
   
		nextNode: 1,
		step:     0,
	}}
	for dist[n][1] == math.MaxInt32 {
          
   
		top := queue[0]
		queue = queue[1:]
		for _, next := range graph[top.nextNode] {
          
   
			cost := top.step + 1
			if cost < dist[next][0] {
          
   
				dist[next][0] = cost
				queue = append(queue, pair{
          
   
					nextNode: next,
					step:     cost,
				})
			} else if dist[next][0] < cost && cost < dist[next][1] {
          
   
				dist[next][1] = cost
				queue = append(queue, pair{
          
   
					nextNode: next,
					step:     cost,
				})
			}
		}
	}
	ans := 0
	for i := 1; i <= dist[n][1]; i++ {
          
   
		if ans%(2*change) >= change {
          
   
			//进入红灯区还需要等待多久才能走
			ans += 2*change - ans%(2*change)
		}
		ans += time
	}
	return ans
}