結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-02-04 01:38:01 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 24 ms / 5,000 ms |
コード長 | 1,093 bytes |
コンパイル時間 | 14,023 ms |
コンパイル使用メモリ | 233,620 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:08:37 |
合計ジャッジ時間 | 15,485 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
package main import ( "fmt" ) func min(x, y int) int { if y < x { return y } return x } type e struct { v int c int t int } func main() { Inf := 1 << 28 var N, C, V int fmt.Scan(&N, &C, &V) var S, T, Y, M [1510]int for i := 0; i < V; i++ { fmt.Scan(&S[i]) } for i := 0; i < V; i++ { fmt.Scan(&T[i]) } for i := 0; i < V; i++ { fmt.Scan(&Y[i]) } for i := 0; i < V; i++ { fmt.Scan(&M[i]) } E := make([][]e, N) for i := 0; i < V; i++ { from, to, cost, time := S[i], T[i], Y[i], M[i] from-- to-- E[from] = append(E[from], e{v: to, c: cost, t: time}) } 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 c0 := C; c0 > 0; c0-- { if dp[i][c0] == Inf { continue } for _, e := range E[i] { if c0-e.c < 0 { continue } dp[e.v][c0-e.c] = min(dp[e.v][c0-e.c], dp[i][c0]+e.t) } } } res := Inf for i := 0; i < C; i++ { res = min(res, dp[N-1][i]) } if res == Inf { res = -1 } fmt.Println(res) }