推 sustainer123: 好爽喔 開大車 07/28 18:00
推 oin1104: 開大車 不要用全型 07/28 18:01
→ JIWP: 歐卡要來玩嗎? 07/28 18:01
→ JIWP: 我要當全形怪人 07/28 18:01
推 sustainer123: 不了 coursera中 07/28 18:26
我寫得好醜
oin救救我
我要繼續開大車了
2045. Second Minimum Time to Reach Destination
就給你一個雙向圖包含1~n
每兩個點間最多只有1條邊
你每經過一條邊需要花time
然後有紅綠燈，只有綠燈才可以走
每經過change燈號會變，開始走的時候都是綠燈
請問從節點1到節點n需要花費第二少的時間是多久
思路 :
就從節點1用BFS開始走
然後在每一次BFS深度時用一個矩陣紀錄這個點有沒有重複到過
就這樣找到花費第二少的深度
這個深度是你從節點1到節點N需要走過的邊數
接著把它變成時間，就可以得到答案了
ＧＯＬＡＮＧ ＣＯＤＥ ：
func secondMinimum(n int, edges [][]int, time int, change int) int {
graph := make([][]int, n+1)
greater := 0
for i := 1; i < n+1; i++ {
graph[i] = make([]int, 0)
}
for _, val := range edges {
graph[val[1]] = append(graph[val[1]], val[0])
graph[val[0]] = append(graph[val[0]], val[1])
}
queue, cnt, prevcnt := make([]int, 1), 0, 0
queue[0] = 1
for len(queue) > 0 {
tmp := len(queue)
reached := make([]bool, n+1)
for tmp > 0 {
cur := queue[0]
queue = queue[1:]
if cur == n && cnt > prevcnt {
greater++
prevcnt = cnt
}
for _, val := range graph[cur] {
if !reached[val] {
queue = append(queue, val)
reached[val] = true
}
}
tmp--
}
if greater == 2 {
break
}
cnt++
}
res, depth := 0, 0
if greater == 1 {
depth = prevcnt + 2
} else {
depth = prevcnt
}
for depth > 1 {
res += time
tmp := res / change
if tmp&1 == 1 {
res = (tmp + 1) * change
}
depth--
}
return res + time
}
GOLANG CODE :
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.129.148 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722160713.A.518.html