結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2020-04-17 01:35:52 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,436 bytes |
コンパイル時間 | 13,833 ms |
コンパイル使用メモリ | 233,280 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:47:04 |
合計ジャッジ時間 | 15,596 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
package main import ( "bufio" "fmt" "os" "strconv" ) type p struct { a int b int c int } var sc = bufio.NewScanner(os.Stdin) func Scanner() string { sc.Scan() return sc.Text() } func main() { buf := make([]byte, 0) sc.Buffer(buf, 100000007) sc.Split(bufio.ScanWords) inm := 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()) } info := make([][]p, n) for i := 0; i < v; i++ { info[s[i]-1] = append(info[s[i]-1], p{a: t[i] - 1, b: y[i], c: m[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] = inm } } dp[0][c] = 0 for i := 0; i < n; i++ { for j := c; j > 0; j-- { if dp[i][j] == inm { continue } for _, p := range info[i] { if j-p.b < 0 { continue } dp[p.a][j-p.b] = min(dp[p.a][j-p.b], dp[i][j]+p.c) } } } ans := inm for i := 0; i < c; i++ { ans = min(ans, dp[n-1][i]) } if ans == inm { ans = -1 } fmt.Println(ans) } func min(x, y int) int { if y < x { return y } return x }