結果

問題 No.1 道のショートカット
ユーザー pessimist
提出日時 2025-01-07 19:00:14
言語 Go
(1.23.4)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,315 bytes
コンパイル時間 18,799 ms
コンパイル使用メモリ 255,044 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-07 19:00:35
合計ジャッジ時間 19,492 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000007)
	sc.Split(bufio.ScanWords)
	inf := 1145141919810
	n, _ := strconv.Atoi(Scanner())
	c, _ := strconv.Atoi(Scanner())
	v, _ := strconv.Atoi(Scanner())
	s := make([]int, v)
	t := make([]int, v)
	y := make([]int, v)
	m := make([]int, v)
	for i := 0; i < v; i++ {
		s[i], _ = strconv.Atoi(Scanner())
	}
	for i := 0; i < v; i++ {
		t[i], _ = strconv.Atoi(Scanner())
	}
	for i := 0; i < v; i++ {
		y[i], _ = strconv.Atoi(Scanner())
	}
	for i := 0; i < v; i++ {
		m[i], _ = strconv.Atoi(Scanner())
	}

	adj := make([][]int, n)
	for i := 0; i < v; i++ {
		adj[s[i]-1] = append(adj[s[i]-1], i)
	}

	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, c+1)
		for j := 0; j <= c; j++ {
			dp[i][j] = inf
		}
	}

	dp[0][c] = 0
	for i := 0; i < n; i++ {
		for j := c; j >= 0; j-- {
			if dp[i][j] == inf {
				continue
			}

			for _, k := range adj[i] {
				if j-y[k] < 0 {
					continue
				}
				dp[t[k]-1][j-y[k]] = min(dp[t[k]-1][j-y[k]], dp[i][j]+m[k])
			}
		}
	}
	ans := inf
	for i := 0; i <= c; i++ {
		ans = min(ans, dp[n-1][i])
	}
	if ans == inf {
		ans = -1
	}
	fmt.Println(ans)
}
0