結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー ID 21712
提出日時 2025-01-25 20:04:09
言語 Go
(1.23.4)
結果
AC  
実行時間 721 ms / 2,000 ms
コード長 1,799 bytes
コンパイル時間 17,099 ms
コンパイル使用メモリ 236,916 KB
実行使用メモリ 31,424 KB
最終ジャッジ日時 2025-01-26 00:05:58
合計ジャッジ時間 32,822 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

type Edge struct {
	cost int64
	a,b int
}

func main() {
	rd:=bf.NewReader(Stdin)
	var n,m,p int
	var y int64
	Fscan(rd,&n,&m,&p,&y)
	graph := make([][]*Edge, n+1)
	for i:=0;i<m;i++ {
		e := new(Edge)
		Fscan(rd, &e.a, &e.b, &e.cost)
		graph[e.a] = append(graph[e.a], e)
		graph[e.b] = append(graph[e.b], e)
	}
	hachi := make([]int64, n+1)
	for i:=0;i<p;i++ {
		var d int
		var x int64
		Fscan(rd,&d,&x)
		hachi[d] = x
	}
	pq := make(PQ, 0, n+1)
	item1 := &Item{id:1,index:-1,cost:0}
	heap.Push(&pq, item1)
	visited := make([]bool, n+1)
	cache := make([]*Item, n+1)
	var ans int64
	for len(pq) > 0 {
		item := heap.Pop(&pq).(*Item)
		visited[item.id] = true
		if hachi[item.id] > 0 {
			nums := (y-item.cost)/hachi[item.id]
			if nums > ans {
				ans = nums
			}
		}
		for _, e := range graph[item.id] {
			next := e.a+e.b-item.id
			if visited[next] {
				continue
			}
			if cache[next] == nil {
				cache[next] = &Item{
					id : next,
					index : -1,
					cost : e.cost + item.cost,
				}
				heap.Push(&pq, cache[next])
			} else {
				newcost := e.cost + item.cost
				if newcost < cache[next].cost {
					cache[next].cost = newcost
					heap.Fix(&pq, cache[next].index)
				}
			}
		}
	}
	Println(ans)
}

type Item struct {
	id int
	index int
	cost int64
}

type PQ []*Item

func (pq PQ)Len() int {
	return len(pq)
}

func (pq PQ)Less(i,j int) bool {
	return pq[i].cost < pq[j].cost
}

func (pq PQ)Swap(i, j int) {
	pq[i],pq[j] = pq[j],pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq*PQ)Push(x any) {
	item := x.(*Item)
	item.index = len(*pq)
	*pq = append(*pq, item)
}

func (pq*PQ)Pop() any {
	old := *pq
	n := len(old)
	*pq = old[:n-1]
	res := old[n-1]
	res.index = -1
	old[n-1] = nil
	return res
}
0