結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー Daniel Agatan
提出日時 2025-04-20 03:35:36
言語 Go
(1.23.4)
結果
TLE  
実行時間 -
コード長 4,708 bytes
コンパイル時間 10,555 ms
コンパイル使用メモリ 244,792 KB
実行使用メモリ 46,524 KB
最終ジャッジ日時 2025-04-20 03:36:01
合計ジャッジ時間 21,097 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 5 TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

/*
	By Raccoon Byte
*/

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func printf(format string, a ...interface{}) { fmt.Fprintf(writer, format, a...) }
func scanf(format string, a ...interface{})  { fmt.Fscanf(reader, format, a...) }

func getInt(num *int) {
	scanf("%d\n", num)
}

func getInt2(num *int, num2 *int) {
	scanf("%d %d\n", num, num2)
}

func getInt3(num *int, num2 *int, num3 *int) {
	scanf("%d %d %d\n", num, num2, num3)
}

func getInt4(num *int, num2 *int, num3 *int, num4 *int) {
	scanf("%d %d %d %d\n", num, num2, num3, num4)
}

func getInt5(num *int, num2 *int, num3 *int, num4 *int, num5 *int) {
	scanf("%d %d %d %d %d\n", num, num2, num3, num4, num5)
}

func getInt6(num *int, num2 *int, num3 *int, num4 *int, num5 *int, num6 *int) {
	scanf("%d %d %d %d %d %d\n", num, num2, num3, num4, num5, num6)
}

func getLine(s *string) {
	line, _ := reader.ReadString('\n')
	*s = line[:len(line)-1]
}

func getString(s *string) {
	scanf("%s\n", s)
}

func getArrInt(arr []int, n int) {
	for i := 0; i < n; i++ {
		scanf("%d", &arr[i])
	}
	scanf("\n")
}

func getArrString(arr []string, n int) {
	for i := 0; i < n; i++ {
		scanf("%s", &arr[i])
	}
	scanf("\n")
}

func printArrInt(arr []int) {
	for i := 0; i < len(arr); i++ {
		if i > 0 {
			printf(" ")
		}

		printf("%d", arr[i])
	}
	printf("\n")
}

func printArrInt2D(arr [][]int) {
	for i := 0; i < len(arr); i++ {
		printArrInt(arr[i])
	}
}

func printArrString(arr []string) {
	for i := 0; i < len(arr); i++ {
		printf("%s\n", arr[i])
	}
}

func abs(num int) int {
	if num >= 0 {
		return num
	}

	return -num
}

func min(num1 int, num2 int) int {
	if num1 <= num2 {
		return num1
	}

	return num2
}

func max(num1 int, num2 int) int {
	if num1 >= num2 {
		return num1
	}

	return num2
}

/*
	End of template
*/

func solve() {
	var n, m, k int
	getInt3(&n, &m, &k)

	values := make([]int, m)
	getArrInt(values, m)

	edges := make(map[int][][2]int, m) // pre-allocate for m edges
	var u, v int
	for i := 0; i < m; i++ {
		getInt2(&u, &v)
		edges[u] = append(edges[u], [2]int{v, values[i]})
		edges[v] = append(edges[v], [2]int{u, values[i]})
	}

	memo := make(map[[2]int]int)
	memo[[2]int{1, 0}] = 0

	minHeap := MinHeap{}
	minHeap.Push(Data{
		value: 0,
		prev:  0,
		u:     1,
		used:  0,
	})

	for !minHeap.IsEmpty() {
		value := minHeap.Peek().value
		prev := minHeap.Peek().prev
		u := minHeap.Peek().u
		used := minHeap.Peek().used
		minHeap.Pop()

		if u == n {
			break
		}
		

		for _, e := range edges[u] {
			v, cost := e[0], e[1]
			if v == prev {
				continue
			}

			if used < k {
				key := [2]int{v, used + 1}
				if _, exist := memo[key]; !exist || value < memo[key] {
					memo[key] = value
					minHeap.Push(Data{
						value: value,
						prev: u,
						u:     v,
						used:  used + 1,
					})
				}
			}

			key := [2]int{v, used}
			if _, exist := memo[key]; !exist || value+cost < memo[key] {
				memo[key] = value + cost
				minHeap.Push(Data{
					value: value + cost,
					prev: u,
					u:     v,
					used:  used,
				})
			}
		}
	}

	result := int(1e15)
	for i := 0; i <= k; i++ { // Correct range
		key := [2]int{n, i}
		if v, exist := memo[key]; exist {
			result = min(result, v)
		}
	}

	if result == int(1e15) {
		result = -1
	}

	printf("%d\n", result)
}

type Data struct {
	value int
	prev  int
	u     int
	used  int
}

type MinHeap struct {
	data []Data
}

func (mh *MinHeap) IsEmpty() bool {
	return len(mh.data) == 0
}

func (mh *MinHeap) heapifyUp(node int) {
	for node > 0 {
		parent := (node - 1) / 2
		if mh.data[node].value >= mh.data[parent].value {
			break
		}

		mh.data[node], mh.data[parent] = mh.data[parent], mh.data[node]
		mh.heapifyUp(parent)
		node = parent
	}
}

func (mh *MinHeap) Push(data Data) {
	mh.data = append(mh.data, data)
	mh.heapifyUp(len(mh.data) - 1)
}

func (mh *MinHeap) heapifyDown(node int) {
	for {
		next := node
		leftChild := node*2 + 1
		rightChild := node*2 + 2

		if leftChild < len(mh.data) && mh.data[next].value > mh.data[leftChild].value {
			next = leftChild
		}

		if rightChild < len(mh.data) && mh.data[next].value > mh.data[rightChild].value {
			next = rightChild
		}

		if node == next {
			break
		}

		mh.data[node], mh.data[next] = mh.data[next], mh.data[node]
		node = next
	}
}

func (mh *MinHeap) Pop() {
	if mh.IsEmpty() {
		return
	}

	mh.data[0] = mh.data[len(mh.data)-1]
	mh.data = mh.data[:len(mh.data)-1]
	mh.heapifyDown(0)
}

func (mh *MinHeap) Peek() Data {
	if mh.IsEmpty() {
		return Data{}
	}

	return mh.data[0]
}

func main() {
	defer writer.Flush()

	tc := 1
	// getInt(&tc)
	for t := 0; t < tc; t++ {
		solve()
	}
}
0