結果

問題 No.3013 ハチマキ買い星人
ユーザー ID 21712
提出日時 2025-01-25 19:51:23
言語 Go
(1.23.4)
結果
MLE  
実行時間 -
コード長 1,406 bytes
コンパイル時間 20,509 ms
コンパイル使用メモリ 261,504 KB
実行使用メモリ 584,704 KB
最終ジャッジ日時 2025-01-26 00:05:33
合計ジャッジ時間 77,643 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28 TLE * 9 MLE * 8
権限があれば一括ダウンロードができます

ソースコード

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)
	heap.Push(&pq, &Item{id:1,cost:0})
	visited := make([]bool, 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
			}
			heap.Push(&pq, &Item{
				id : next,
				cost : e.cost + item.cost,
			})
		}
	}
	Println(ans)
}

type Item struct {
	id 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]
}

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

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