結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2016-10-31 12:31:38 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 2,444 ms |
コンパイル使用メモリ | 108,288 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-07-20 16:27:13 |
合計ジャッジ時間 | 4,665 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Magatro { static int N, C, V; static int[] S, T, Y, M; static void Main() { Read(); long[,] dp = new long[N+1, C + 1]; for(int i = 0; i < N + 1; i++) { for(int j = 0; j < C + 1; j++) { dp[i, j] = int.MaxValue; } } dp[1, 0] = 0; for(int i = 1; i <= N; i++) { for(int j = 0; j < V; j++) { if (S[j] == i) { for(int q = 0; q <= C; q++) { if (dp[i, q] != int.MaxValue) { if (q + Y[j] <= C) { dp[T[j], q + Y[j]] = Math.Min(dp[i, q] + M[j], dp[T[j], q + Y[j]]); } } } } } } long min = int.MaxValue; bool a = true ; for(int i = 0; i <= C; i++) { if (dp[N, i] != int.MaxValue) { min = Math.Min(min, dp[N, i]); a = false; } } if (a) { min = -1; } Console.WriteLine(min); } static void Read() { N = int.Parse(Console.ReadLine()); C = int.Parse(Console.ReadLine()); V = int.Parse(Console.ReadLine()); S = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray(); T = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray(); Y = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray(); M = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray(); } }