結果
問題 | No.1868 Teleporting Cyanmond |
ユーザー |
|
提出日時 | 2024-02-09 10:51:17 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 5,667 bytes |
コンパイル時間 | 10,325 ms |
コンパイル使用メモリ | 224,448 KB |
実行使用メモリ | 84,224 KB |
最終ジャッジ日時 | 2024-09-28 12:57:55 |
合計ジャッジ時間 | 13,984 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
package mainimport ("bufio""fmt""os")const INF int = 1e18func main() {yuki1868()}func yuki1868() {// https://yukicoder.me/problems/no/1868// !给定一张有向图,每个点i可以向右达到i+1,i+2,...,targets[i]。求从0到n-1的最短路。// 解法1:每个点i连接targets[i],边权为1,所有i到i-1连边,边权为0。然后跑最短路。(前后缀优化建图)// 解法2:RangeToRangeGraph。每个点i连接i+1,i+2,...,targets[i]。然后跑最短路。in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n intfmt.Fscan(in, &n)targets := make([]int, n-1) // !从i可以到 i+1, i+2, ..., targets[i]for i := range targets {fmt.Fscan(in, &targets[i])targets[i]-- // [0,n-1]内}R := NewRangeToRangeGraph(n)for i := 0; i < n-1; i++ {R.AddToRange(i, i+1, targets[i]+1, 1) // 左闭右开}adjList, newN := R.Build()dist, queue := make([]int, newN), NewDeque(newN)for i := range dist {dist[i] = INF}dist[0] = 0queue.Append(0)for queue.Size() > 0 {cur := queue.PopLeft()for _, e := range adjList[cur] {next, weight := e[0], e[1]cand := dist[cur] + weightif cand < dist[next] {dist[next] = candif weight == 0 {queue.AppendLeft(next)} else {queue.Append(next)}}}}fmt.Fprintln(out, dist[n-1])}func jump(nums []int) int {// 45. 跳跃游戏 II// https://leetcode.cn/problems/jump-game-ii/n := len(nums)G := NewRangeToRangeGraph(n)for i := 0; i < n; i++ {G.AddToRange(i, i+1, min(i+nums[i]+1, n), 1)}adjList, _ := G.Build()bfs := func(start int, adjList [][][2]int) []int {n := len(adjList)dist := make([]int, n)for i := 0; i < n; i++ {dist[i] = INF}dist[start] = 0queue := []int{start}for len(queue) > 0 {cur := queue[0]queue = queue[1:]for _, e := range adjList[cur] {next, weight := e[0], e[1]cand := dist[cur] + weightif cand < dist[next] {dist[next] = candqueue = append(queue, next)}}}return dist}dist := bfs(0, adjList)return dist[n-1]}func min(a, b int) int {if a < b {return a}return b}type edge struct {from, to int32weight int32}type RangeToRangeGraph struct {n int32nNode intedges []edge}func NewRangeToRangeGraph(n int) *RangeToRangeGraph {n32 := int32(n)g := &RangeToRangeGraph{n: n32,nNode: n * 3,}for i := int32(2); i < n32+n32; i++ {g.edges = append(g.edges, edge{from: g.toUpperIdx(i / 2), to: g.toUpperIdx(i), weight: 0})}for i := int32(2); i < n32+n32; i++ {g.edges = append(g.edges, edge{from: g.toLowerIdx(i), to: g.toLowerIdx(i / 2), weight: 0})}return g}// 添加有向边 from -> to, 权重为 weight.func (g *RangeToRangeGraph) Add(from, to int, weight int) {g.edges = append(g.edges, edge{from: int32(from), to: int32(to), weight: int32(weight)})}// 从区间 [fromStart, fromEnd) 中的每个点到 to 都添加一条有向边,权重为 weight.func (g *RangeToRangeGraph) AddFromRange(fromStart, fromEnd, to int, weight int) {l, r := int32(fromStart)+g.n, int32(fromEnd)+g.nfor l < r {if l&1 == 1 {g.Add(int(g.toLowerIdx(l)), to, weight)l++}if r&1 == 1 {r--g.Add(int(g.toLowerIdx(r)), to, weight)}l >>= 1r >>= 1}}// 从 from 到区间 [toStart, toEnd) 中的每个点都添加一条有向边,权重为 weight.func (g *RangeToRangeGraph) AddToRange(from, toStart, toEnd int, weight int) {l, r := int32(toStart)+g.n, int32(toEnd)+g.nfor l < r {if l&1 == 1 {g.Add(from, int(g.toUpperIdx(l)), weight)l++}if r&1 == 1 {r--g.Add(from, int(g.toUpperIdx(r)), weight)}l >>= 1r >>= 1}}// 从区间 [fromStart, fromEnd) 中的每个点到区间 [toStart, toEnd) 中的每个点都添加一条有向边,权重为 weight.func (g *RangeToRangeGraph) AddRangeToRange(fromStart, fromEnd, toStart, toEnd int, weight int) {newNode := g.nNodeg.nNode++g.AddFromRange(fromStart, fromEnd, newNode, weight)g.AddToRange(newNode, toStart, toEnd, 0)}// 返回`新图的有向邻接表和新图的节点数`.func (g *RangeToRangeGraph) Build() (graph [][][2]int, vertex int) {graph = make([][][2]int, g.nNode)for i := 0; i < len(g.edges); i++ {e := &g.edges[i]u, v, w := e.from, e.to, e.weightgraph[u] = append(graph[u], [2]int{int(v), int(w)})}return graph, g.nNode}func (g *RangeToRangeGraph) toUpperIdx(i int32) int32 {if i >= g.n {return i - g.n}return g.n + i}func (g *RangeToRangeGraph) toLowerIdx(i int32) int32 {if i >= g.n {return i - g.n}return g.n + g.n + i}type D = inttype Deque struct{ l, r []D }func NewDeque(cap int) *Deque { return &Deque{make([]D, 0, 1+cap/2), make([]D, 0, 1+cap/2)} }func (q Deque) Empty() bool {return len(q.l) == 0 && len(q.r) == 0}func (q Deque) Size() int {return len(q.l) + len(q.r)}func (q *Deque) AppendLeft(v D) {q.l = append(q.l, v)}func (q *Deque) Append(v D) {q.r = append(q.r, v)}func (q *Deque) PopLeft() (v D) {if len(q.l) > 0 {q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]} else {v, q.r = q.r[0], q.r[1:]}return}func (q *Deque) Pop() (v D) {if len(q.r) > 0 {q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]} else {v, q.l = q.l[0], q.l[1:]}return}func (q Deque) Front() D {if len(q.l) > 0 {return q.l[len(q.l)-1]}return q.r[0]}func (q Deque) Back() D {if len(q.r) > 0 {return q.r[len(q.r)-1]}return q.l[0]}// 0 <= i < q.Size()func (q Deque) At(i int) D {if i < len(q.l) {return q.l[len(q.l)-1-i]}return q.r[i-len(q.l)]}