結果

問題 No.3111 Toll Optimization
ユーザー Daniel Agatan
提出日時 2025-04-20 03:45:14
言語 Go
(1.23.4)
結果
AC  
実行時間 380 ms / 5,000 ms
コード長 3,309 bytes
コンパイル時間 12,975 ms
コンパイル使用メモリ 236,116 KB
実行使用メモリ 34,764 KB
最終ジャッジ日時 2025-04-20 03:45:44
合計ジャッジ時間 24,770 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

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 getArrInt(arr []int, n int) {
	for i := 0; i < n; i++ {
		scanf("%d", &arr[i])
	}
	scanf("\n")
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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]
		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
		left := 2*node + 1
		right := 2*node + 2

		if left < len(mh.data) && mh.data[left].value < mh.data[next].value {
			next = left
		}
		if right < len(mh.data) && mh.data[right].value < mh.data[next].value {
			next = right
		}
		if next == node {
			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 {
	return mh.data[0]
}

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)
	for i := 0; i < m; i++ {
		var u, v int
		getInt2(&u, &v)
		edges[u] = append(edges[u], [2]int{v, values[i]})
		edges[v] = append(edges[v], [2]int{u, values[i]})
	}

	const inf = int(1e18)
	memo := make([][]int, n+1)
	for i := range memo {
		memo[i] = make([]int, k+1)
		for j := range memo[i] {
			memo[i][j] = inf
		}
	}
	memo[1][0] = 0

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

	for !minHeap.IsEmpty() {
		cur := minHeap.Peek()
		minHeap.Pop()

		if cur.value > memo[cur.u][cur.used] {
			continue
		}

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

			// Option 1: use free pass if available
			if cur.used < k && cur.value < memo[v][cur.used+1] {
				memo[v][cur.used+1] = cur.value
				minHeap.Push(Data{
					value: cur.value,
					prev:  cur.u,
					u:     v,
					used:  cur.used + 1,
				})
			}

			// Option 2: pay the cost
			if cur.value+cost < memo[v][cur.used] {
				memo[v][cur.used] = cur.value + cost
				minHeap.Push(Data{
					value: cur.value + cost,
					prev:  cur.u,
					u:     v,
					used:  cur.used,
				})
			}
		}
	}

	result := inf
	for i := 0; i <= k; i++ {
		result = min(result, memo[n][i])
	}
	if result == inf {
		result = -1
	}
	printf("%d\n", result)
}

func main() {
	defer writer.Flush()
	solve()
}
0