結果
問題 | No.1868 Teleporting Cyanmond |
ユーザー |
|
提出日時 | 2024-04-11 23:30:23 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 4,652 bytes |
コンパイル時間 | 14,746 ms |
コンパイル使用メモリ | 226,540 KB |
実行使用メモリ | 16,384 KB |
最終ジャッジ日時 | 2024-10-02 21:45:22 |
合計ジャッジ時間 | 17,176 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
// 前后缀优化建图1 - 点向区间连边.//// PointToPrefixSuffix// 3 → 4 → 5 (后缀)// ↓ ↓ ↓// 0 1 2// ↑ ↑ ↑// 6 ← 7 ← 8 (前缀)package mainimport ("bufio""fmt""os")const INF32 int32 = 1e9 + 10func main() {yuki1868()}func yuki1868() {// https://yukicoder.me/problems/no/1868// !给定一张有向图,每个点i可以向右达到i+1,i+2,...,targets[i]。求从0到n-1的最短路。(前后缀优化建图)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 := NewRangeToRangeGraphOnPrefixSuffix1(n)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.AddPointToPrefix(i, targets[i]+1, func(from, to int32) {adjList[from] = append(adjList[from], Neighbor{to, 1})})}dist := Bfs0132(adjList, 0)fmt.Fprintln(out, dist[n-1])}func demo() {n := int32(3)R := NewRangeToRangeGraphOnPrefixSuffix1(n)newGraph := make([][]Neighbor, R.Size())R.Init(func(from, to int32) { // from -> tonewGraph[from] = append(newGraph[from], Neighbor{to, 0})})R.AddPointToPrefix(2, 2, func(from, to int32) { // from -> [0,prefixEnd)newGraph[from] = append(newGraph[from], Neighbor{to, 1})})R.AddPointToSuffix(0, 0, func(from, to int32) { // from -> [suffixStart,n)newGraph[from] = append(newGraph[from], Neighbor{to, 1})})fmt.Println(newGraph)dist := Bfs0132(newGraph, 2)fmt.Println(dist[:n])dist = Bfs0132(newGraph, 0)fmt.Println(dist[:n])}type RangeToRangeGraphOnPrefixSuffix1 struct {n int32maxSize int32 // [0,n):原始点,[n,n*2):后缀点,[n*2,n*3):前缀点.}// 新建一个区间图,n 为原图的节点数.func NewRangeToRangeGraphOnPrefixSuffix1(n int32) *RangeToRangeGraphOnPrefixSuffix1 {return &RangeToRangeGraphOnPrefixSuffix1{n: n, maxSize: 3 * n}}// 新图的结点数.前n个节点为原图的节点.func (g *RangeToRangeGraphOnPrefixSuffix1) Size() int32 { return g.maxSize }func (g *RangeToRangeGraphOnPrefixSuffix1) Init(f func(from, to int32)) {n1, n2 := g.n, g.n*2for i := int32(0); i < n1; i++ {f(i+n1, i)f(i+n2, i)if i > 0 {f(i+n1-1, i+n1)f(i+n2, i+n2-1)}}}// 添加有向边 from -> to.func (g *RangeToRangeGraphOnPrefixSuffix1) Add(from, to int32, f func(from, to int32)) {f(from, to)}// from -> [0,prefixEnd)func (g *RangeToRangeGraphOnPrefixSuffix1) AddPointToPrefix(from int32, prefixEnd int32, f func(from, to int32)) {if prefixEnd <= 0 {return}f(from, g.n*2+prefixEnd-1)}// from -> [suffixStart,n)func (g *RangeToRangeGraphOnPrefixSuffix1) AddPointToSuffix(from int32, suffixStart int32, f func(from, to int32)) {if suffixStart >= g.n {return}f(from, g.n+suffixStart)}type Neighbor struct {next int32dist int8}// 01bfs求最短路.func Bfs0132(adjList [][]Neighbor, start int32) []int32 {n := int32(len(adjList))dist := make([]int32, n)for i := range dist {dist[i] = INF32}dist[start] = 0queue := NewDeque(n)queue.Append(start)for queue.Size() > 0 {cur := queue.PopLeft()for _, edge := range adjList[cur] {next, weight := edge.next, edge.distcand := dist[cur] + int32(weight)if cand < dist[next] {dist[next] = candif weight == 0 {queue.AppendLeft(next)} else {queue.Append(next)}}}}return dist}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)]}