結果

問題 No.1 道のショートカット
ユーザー AreTrashAreTrash
提出日時 2016-06-25 20:04:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 44 ms / 5,000 ms
コード長 3,201 bytes
コンパイル時間 1,024 ms
コンパイル使用メモリ 114,112 KB
実行使用メモリ 20,864 KB
最終ジャッジ日時 2024-07-20 16:24:04
合計ジャッジ時間 3,812 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
19,712 KB
testcase_01 AC 34 ms
19,584 KB
testcase_02 AC 34 ms
19,328 KB
testcase_03 AC 35 ms
19,456 KB
testcase_04 AC 34 ms
19,584 KB
testcase_05 AC 34 ms
19,584 KB
testcase_06 AC 34 ms
19,584 KB
testcase_07 AC 34 ms
19,584 KB
testcase_08 AC 41 ms
20,480 KB
testcase_09 AC 39 ms
20,352 KB
testcase_10 AC 41 ms
20,480 KB
testcase_11 AC 42 ms
20,352 KB
testcase_12 AC 42 ms
20,608 KB
testcase_13 AC 42 ms
20,864 KB
testcase_14 AC 35 ms
19,456 KB
testcase_15 AC 34 ms
19,328 KB
testcase_16 AC 40 ms
20,096 KB
testcase_17 AC 35 ms
19,584 KB
testcase_18 AC 36 ms
19,584 KB
testcase_19 AC 34 ms
19,328 KB
testcase_20 AC 38 ms
19,968 KB
testcase_21 AC 41 ms
19,968 KB
testcase_22 AC 35 ms
19,584 KB
testcase_23 AC 42 ms
20,480 KB
testcase_24 AC 41 ms
20,352 KB
testcase_25 AC 39 ms
20,224 KB
testcase_26 AC 40 ms
20,096 KB
testcase_27 AC 44 ms
20,480 KB
testcase_28 AC 35 ms
19,456 KB
testcase_29 AC 41 ms
20,608 KB
testcase_30 AC 40 ms
19,968 KB
testcase_31 AC 40 ms
19,840 KB
testcase_32 AC 41 ms
20,352 KB
testcase_33 AC 41 ms
20,352 KB
testcase_34 AC 42 ms
20,608 KB
testcase_35 AC 41 ms
19,968 KB
testcase_36 AC 42 ms
20,096 KB
testcase_37 AC 40 ms
19,968 KB
testcase_38 AC 35 ms
19,584 KB
testcase_39 AC 39 ms
19,968 KB
testcase_40 AC 40 ms
19,968 KB
testcase_41 AC 38 ms
19,968 KB
testcase_42 AC 34 ms
19,584 KB
testcase_43 AC 34 ms
19,456 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Linq;
namespace No1{
public class Program{
public static void Main(string[] args){
var sr = new StreamReader();
//---------------------------------
var N = sr.Next<int>();//
var C = sr.Next<int>();//
var V = sr.Next<int>();//
var Rv = sr.Next<int>(4, V).Transpose()
.Select(a => new {from = a[0], to = a[1], cost = a[2], time = a[3]}).OrderBy(a => a.to);
var dp = new int[N + 1, C + 1].ToJaggedArray();
dp[1][0] = 1;
foreach(var r in Rv){
for(var i = r.cost; i <= C; i++){
if(dp[r.from][i - r.cost] != 0) {
if(dp[r.to][i] == 0 || dp[r.to][i] > dp[r.from][i - r.cost] + r.time){
dp[r.to][i] = dp[r.from][i - r.cost] + r.time;
}
}
}
}
Console.WriteLine(dp[N].Where(x => x != 0).DefaultIfEmpty(0).Min() - 1);
//---------------------------------
}
}
public static class ExMethod{
public static T[][] Transpose<T>(this T[][] src){
var x = src.Length;
var y = src[0].Length;
var ret = new T[y][];
for(var i = 0; i < y; i++){
ret[i] = new T[x];
for(var j = 0; j < x; j++){
ret[i][j] = src[j][i];
}
}
return ret;
}
public static T[][] ToJaggedArray<T>(this T[,] src){
var x = src.GetLength(1);
var y = src.GetLength(0);
var ret = new T[y][];
for(var i = 0; i < y; i++){
ret[i] = new T[x];
for(var j = 0; j < x; j++){
ret[i][j] = src[i, j];
}
}
return ret;
}
}
public class StreamReader{
private readonly char[] _c = {' '};
private int _index = -1;
private string[] _input = new string[0];
public T Next<T>(){
if(_index == _input.Length - 1){
_index = -1;
while(true){
string rl = Console.ReadLine();
if(rl == null){
if(typeof(T).IsClass) return default(T);
return (T)typeof(T).GetField("MinValue").GetValue(null);
}
if(rl != ""){
_input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
break;
}
}
}
return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
}
public T[] Next<T>(int x){
var ret = new T[x];
for(var i = 0; i < x; ++i) ret[i] = Next<T>();
return ret;
}
public T[][] Next<T>(int y, int x){
var ret = new T[y][];
for(var i = 0; i < y; ++i) ret[i] = Next<T>(x);
return ret;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0