結果

問題 No.1995 CHIKA Road
ユーザー ID 21712
提出日時 2025-05-15 22:49:10
言語 Go
(1.23.4)
結果
AC  
実行時間 313 ms / 2,000 ms
コード長 1,158 bytes
コンパイル時間 13,784 ms
コンパイル使用メモリ 232,916 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2025-05-15 22:49:32
合計ジャッジ時間 21,027 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "os"
import bf "bufio"
import "container/heap"

func main() {
	rd:=bf.NewReader(Stdin)
	var n,m int
	Fscan(rd,&n,&m)
	pq := make(PQ, 0, 2*m+2)
	for i := 0; i < m; i++ {
		var a, b int
		Fscan(rd,&a,&b)
		heap.Push(&pq, &Jump{a, b})
	}
	cur := 1
	cost := 0
	for pq.Len() > 0 {
		switch item := heap.Pop(&pq).(type) {
			case *Jump:
				heap.Push(&pq, &Reach{
					pos: item.to,
					cost: cost + 2*(item.to-cur)-1,
				})
			case *Reach:
				cost = min(cost+2*(item.pos-cur), item.cost)
				cur = item.pos
		}
	}
	cost += 2*(n-cur)
	Println(cost)
}

type Jump struct {
	from, to int
}
func (j *Jump) Value() int { return j.from*2+1 }

type Reach struct {
	pos, cost int
}
func (r *Reach) Value() int { return r.pos*2 }

type Item interface { Value() int }

type PQ []Item

func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].Value() < pq[j].Value() }
func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x any) {
	*pq = append(*pq, x.(Item))
}
func (pq *PQ) Pop() any {
	old := *pq
	n := len(old)
	x := old[n-1]
	old[n-1] = nil
	*pq = old[:n-1]
	return x
}
0