#10950 (Go) No.1 道のショートカット

• 問題: No.1 道のショートカット
• ユーザー: tnoda_
• 提出日時: 2015-02-04 00:57:19
• 言語: Go (1.22.1)
• 結果: WA
• 実行時間: -
• コード長: 1,133 bytes
• コンパイル時間: 12,837 ms
• コンパイル使用メモリ: 224,188 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-08 03:44:39
• 合計ジャッジ時間: 14,430 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	18 ms; 5,376 KB
testcase_09	AC	15 ms; 5,376 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	1 ms; 5,376 KB
testcase_16	WA	-
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	3 ms; 5,376 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	4 ms; 5,376 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	6 ms; 5,376 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	2 ms; 5,376 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	12 ms; 5,376 KB
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	AC	3 ms; 5,376 KB
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	AC	2 ms; 5,376 KB
testcase_43	AC	2 ms; 5,376 KB

ソースコード

package main

import (
	"fmt"
)

const (
	inf  = 1 << 28
	maxN = 52
	maxC = 310
)

func min(x, y int) int {
	if y < x {
		return y
	}
	return x
}

func main() {
	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])
	}
	var cost, time [maxN][maxN]int
	for i := 0; i < maxN; i++ {
		for j := 0; j < maxN; j++ {
			cost[i][j] = inf
			time[i][j] = inf
		}
	}
	for i := 0; i < V; i++ {
		cost[S[i]][T[i]] = Y[i]
		time[S[i]][T[i]] = M[i]
	}
	var dp [maxN][maxC]int
	for i := 0; i < maxN; i++ {
		for j := 0; j < maxC; j++ {
			dp[i][j] = inf
		}
	}
	dp[1][0] = 0
	for from := 1; from < N; from++ {
		for c0 := 0; c0 < C; c0++ {
			for to := from + 1; to <= N; to++ {
				dc := cost[from][to]
				dt := time[from][to]
				c1 := c0 + dc
				if c1 <= C {
					dp[to][c1] = min(dp[to][c1], dp[from][c0]+dt)
				}
			}
		}
	}
	res := inf
	for i := 1; i <= C; i++ {
		res = min(res, dp[N][i])
	}
	if res == inf {
		res = -1
	}
	fmt.Println(res)
}