結果
問題 | No.1868 Teleporting Cyanmond |
ユーザー |
|
提出日時 | 2024-04-10 22:35:09 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 9,718 bytes |
コンパイル時間 | 10,459 ms |
コンパイル使用メモリ | 223,092 KB |
実行使用メモリ | 55,168 KB |
最終ジャッジ日時 | 2024-10-02 21:02:48 |
合計ジャッジ時間 | 14,048 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
// RangeToRangeGraph (区间图)// !原图的连通分量/最短路在新图上仍然等价// 线段树优化建图package mainimport ("bufio""fmt""os")const INF int = 1e18func main() {// CF786B()yuki1868()}// https://www.luogu.com.cn/problem/CF786Bfunc CF786B() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n, q, start int32fmt.Fscan(in, &n, &q, &start)start--G := NewRangeToRangeGraph(n, 0)newGraph := make([][]neighbor, G.Size())G.Init(func(from, to int32) { newGraph[from] = append(newGraph[from], neighbor{to, 0}) })for i := int32(0); i < q; i++ {var op int32fmt.Fscan(in, &op)if op == 1 {var from, to int32var weight intfmt.Fscan(in, &from, &to, &weight)from--to--G.Add(from, to, func(from, to int32) {newGraph[from] = append(newGraph[from], neighbor{to, weight})})} else if op == 2 {var from, l, r int32var weight intfmt.Fscan(in, &from, &l, &r, &weight)from--l--G.AddToRange(from, l, r, func(from, to int32) {newGraph[from] = append(newGraph[from], neighbor{to, weight})})} else if op == 3 {var to, l, r int32var weight intfmt.Fscan(in, &to, &l, &r, &weight)to--l--G.AddFromRange(l, r, to, func(from, to int32) {newGraph[from] = append(newGraph[from], neighbor{to, weight})})}}res := DijkstraInt32(int32(len(newGraph)), newGraph, start)for i := int32(0); i < n; i++ {fmt.Fprint(out, res[i], " ")}}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 int32fmt.Fscan(in, &n)targets := make([]int32, 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, 0)adjList := make([][]neighbor, R.Size())R.Init(func(from, to int32) {adjList[from] = append(adjList[from], neighbor{to, 0})})for i := int32(0); i < n-1; i++ {R.AddToRange(i, i+1, targets[i]+1, func(from, to int32) {adjList[from] = append(adjList[from], neighbor{to, 1})})}dist, queue := make([]int, int32(len(adjList))), NewDeque(int32(len(adjList)))for i := range dist {dist[i] = INF}dist[0] = 0queue.Append(0)for queue.Size() > 0 {cur := queue.PopLeft()nexts := adjList[cur]for i := 0; i < len(nexts); i++ {e := &nexts[i]next, weight := e.to, e.weightcand := 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 := int32(len(nums))G := NewRangeToRangeGraph(int32(n), 0)adjList := make([][]neighbor, G.Size())G.Init(func(from, to int32) { adjList[from] = append(adjList[from], neighbor{to, 0}) })for i := int32(0); i < n; i++ {G.AddToRange(i, i+1, min32(i+1+int32(nums[i]), n), func(from, to int32) {adjList[from] = append(adjList[from], neighbor{to, 1})})}bfs := func(start int32, adjList [][]neighbor) []int32 {n := len(adjList)dist := make([]int32, n)for i := 0; i < n; i++ {dist[i] = 1e9}dist[start] = 0queue := []int32{start}for len(queue) > 0 {cur := queue[0]queue = queue[1:]nexts := adjList[cur]for i := 0; i < len(nexts); i++ {e := &nexts[i]next, weight := e.to, e.weightcand := dist[cur] + int32(weight)if cand < dist[next] {dist[next] = candqueue = append(queue, next)}}}return dist}dist := bfs(0, adjList)return int(dist[n-1])}type RangeToRangeGraph struct {n int32maxSize int32allocPtr int32}// 新建一个区间图,n 为原图的节点数,rangeToRangeOpCount 为区间到区间的最大操作次数.// 最后得到的新图的节点数为 n*3 + rangeToRangeOpCount,前n个节点为原图的节点。func NewRangeToRangeGraph(n int32, rangeToRangeOpCount int32) *RangeToRangeGraph {g := &RangeToRangeGraph{n: n,maxSize: n*3 + rangeToRangeOpCount,allocPtr: n * 3,}return g}func (g *RangeToRangeGraph) Init(f func(from, to int32)) {n := g.nfor i := int32(2); i < n+n; i++ {f(g.toUpperIdx(i>>1), g.toUpperIdx(i))f(g.toLowerIdx(i), g.toLowerIdx(i>>1))}}// 添加有向边 from -> to.func (g *RangeToRangeGraph) Add(from, to int32, f func(from, to int32)) {f(from, to)}// 从区间 [fromStart, fromEnd) 中的每个点到 to 都添加一条有向边.func (g *RangeToRangeGraph) AddFromRange(fromStart, fromEnd, to int32, f func(from, to int32)) {l, r := fromStart+g.n, fromEnd+g.nfor l < r {if l&1 == 1 {f(g.toLowerIdx(l), to)l++}if r&1 == 1 {r--f(g.toLowerIdx(r), to)}l >>= 1r >>= 1}}// 从 from 到区间 [toStart, toEnd) 中的每个点都添加一条有向边.func (g *RangeToRangeGraph) AddToRange(from, toStart, toEnd int32, f func(from, to int32)) {l, r := toStart+g.n, toEnd+g.nfor l < r {if l&1 == 1 {f(from, g.toUpperIdx(l))l++}if r&1 == 1 {r--f(from, g.toUpperIdx(r))}l >>= 1r >>= 1}}// 从区间 [fromStart, fromEnd) 中的每个点到区间 [toStart, toEnd) 中的每个点都添加一条有向边.func (g *RangeToRangeGraph) AddRangeToRange(fromStart, fromEnd, toStart, toEnd int32, f func(from, to int32)) {newNode := g.allocPtrg.allocPtr++g.AddFromRange(fromStart, fromEnd, newNode, f)g.AddToRange(newNode, toStart, toEnd, f)}// 新图的结点数.func (g *RangeToRangeGraph) Size() int32 { return g.maxSize }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 = int32type Deque struct{ l, r []D }func NewDeque(cap int32) *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)]}type neighbor struct {to int32weight int}// 如果不存在则返回 -1.func DijkstraInt32(n int32, graph [][]neighbor, start int32) []int {pq := NewHeap(func(a, b H) bool { return a.dist < b.dist }, []H{{0, start}})dist := make([]int, n)for i := range dist {dist[i] = INF}dist[start] = 0for pq.Len() > 0 {cur := pq.Pop()curDist, curNode := cur.dist, cur.nodeif curDist > dist[curNode] {continue}nexts := graph[curNode]for i := 0; i < len(nexts); i++ {e := &nexts[i]next, weight := e.to, e.weightif tmp := curDist + weight; tmp < dist[next] {dist[next] = tmppq.Push(H{tmp, next})}}}for i := range dist {if dist[i] == INF {dist[i] = -1}}return dist}type H = struct {dist intnode int32}func NewHeap(less func(a, b H) bool, nums []H) *Heap {nums = append(nums[:0:0], nums...)heap := &Heap{less: less, data: nums}heap.heapify()return heap}type Heap struct {data []Hless func(a, b H) bool}func (h *Heap) Push(value H) {h.data = append(h.data, value)h.pushUp(h.Len() - 1)}func (h *Heap) Pop() (value H) {if h.Len() == 0 {panic("heap is empty")}value = h.data[0]h.data[0] = h.data[h.Len()-1]h.data = h.data[:h.Len()-1]h.pushDown(0)return}func (h *Heap) Top() (value H) {value = h.data[0]return}func (h *Heap) Len() int { return len(h.data) }func (h *Heap) heapify() {n := h.Len()for i := (n >> 1) - 1; i > -1; i-- {h.pushDown(i)}}func (h *Heap) pushUp(root int) {for parent := (root - 1) >> 1; parent >= 0 && h.less(h.data[root], h.data[parent]); parent = (root - 1) >> 1 {h.data[root], h.data[parent] = h.data[parent], h.data[root]root = parent}}func (h *Heap) pushDown(root int) {n := h.Len()for left := (root<<1 + 1); left < n; left = (root<<1 + 1) {right := left + 1minIndex := rootif h.less(h.data[left], h.data[minIndex]) {minIndex = left}if right < n && h.less(h.data[right], h.data[minIndex]) {minIndex = right}if minIndex == root {return}h.data[root], h.data[minIndex] = h.data[minIndex], h.data[root]root = minIndex}}func min(a, b int) int {if a < b {return a}return b}func max(a, b int) int {if a > b {return a}return b}func min32(a, b int32) int32 {if a < b {return a}return b}func max32(a, b int32) int32 {if a > b {return a}return b}