結果
問題 | No.1 道のショートカット |
ユーザー | nokonoko |
提出日時 | 2017-10-03 22:59:38 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,859 bytes |
コンパイル時間 | 2,487 ms |
コンパイル使用メモリ | 109,732 KB |
実行使用メモリ | 25,928 KB |
最終ジャッジ日時 | 2023-09-22 13:15:11 |
合計ジャッジ時間 | 7,281 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
21,852 KB |
testcase_01 | AC | 66 ms
21,720 KB |
testcase_02 | AC | 66 ms
21,796 KB |
testcase_03 | AC | 66 ms
21,776 KB |
testcase_04 | AC | 65 ms
21,664 KB |
testcase_05 | AC | 64 ms
21,852 KB |
testcase_06 | AC | 66 ms
21,920 KB |
testcase_07 | AC | 66 ms
23,736 KB |
testcase_08 | AC | 76 ms
23,928 KB |
testcase_09 | AC | 74 ms
21,908 KB |
testcase_10 | AC | 75 ms
21,912 KB |
testcase_11 | AC | 78 ms
22,132 KB |
testcase_12 | AC | 76 ms
21,956 KB |
testcase_13 | AC | 77 ms
24,044 KB |
testcase_14 | WA | - |
testcase_15 | RE | - |
testcase_16 | AC | 73 ms
21,776 KB |
testcase_17 | AC | 65 ms
21,712 KB |
testcase_18 | AC | 66 ms
21,712 KB |
testcase_19 | AC | 66 ms
21,828 KB |
testcase_20 | AC | 72 ms
19,908 KB |
testcase_21 | AC | 72 ms
22,040 KB |
testcase_22 | AC | 66 ms
21,860 KB |
testcase_23 | WA | - |
testcase_24 | AC | 78 ms
21,944 KB |
testcase_25 | AC | 75 ms
23,876 KB |
testcase_26 | AC | 73 ms
23,832 KB |
testcase_27 | AC | 75 ms
19,980 KB |
testcase_28 | AC | 66 ms
19,660 KB |
testcase_29 | AC | 76 ms
22,132 KB |
testcase_30 | AC | 74 ms
24,032 KB |
testcase_31 | AC | 78 ms
21,984 KB |
testcase_32 | AC | 75 ms
23,952 KB |
testcase_33 | AC | 74 ms
25,928 KB |
testcase_34 | AC | 78 ms
24,016 KB |
testcase_35 | AC | 73 ms
21,928 KB |
testcase_36 | AC | 74 ms
23,960 KB |
testcase_37 | AC | 74 ms
21,904 KB |
testcase_38 | AC | 66 ms
21,776 KB |
testcase_39 | AC | 73 ms
21,844 KB |
testcase_40 | AC | 74 ms
21,848 KB |
testcase_41 | AC | 74 ms
23,952 KB |
testcase_42 | AC | 65 ms
21,720 KB |
testcase_43 | RE | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Linq; using System.Text; using System.Collections.Generic; using STR = System.String; using INT = System.Int32; using DEC = System.Double; class Program { public static IO IO = new IO(); public struct DATA { public INT N; public INT T; public INT Y; public INT M; public DATA(INT n, INT t, INT y, INT m) { N = n; T = t; Y = y; M =m; } public bool SAME(DATA t) { return T == t.T && Y == t.Y; } } static void Main(string[] args) { INT n = IO.I(); INT c = IO.I(); INT v = IO.I(); INT[] s = IO.I(' '); INT[] t = IO.I(' '); INT[] y = IO.I(' '); INT[] m = IO.I(' '); INT[] tmin = new INT[n]; Dictionary<INT, List<DATA>> data = new Dictionary<int, List<DATA>>(); QUEUE<DATA> que = new QUEUE<DATA>(v); for (int i = 0; i < v; i++) { if (!data.Keys.Contains(s[i])) { data[s[i]] = new List<DATA>(); } data[s[i]].Add(new DATA(i, t[i], y[i], m[i])); } for (int i = 0; i < n; i++) { tmin[i] = INT.MaxValue; } for (int i = 0; i < data[1].Count(); i++) { que.PUSH(data[1][i]); } while (que.SIZE() != 0) { DATA x = que.POP(); if ((x.Y <= c) && (tmin[x.T - 1] > x.M)) { tmin[x.T - 1] = x.M; } if (data.ContainsKey(x.T)) { for (int i = 0; i < data[x.T].Count(); i++) { DATA buf = data[x.T][i]; if ((buf.Y + x.Y <= c) && (tmin[buf.T - 1] > buf.M + x.M)) { que.PUSH(new DATA(buf.N, buf.T, buf.Y + x.Y, buf.M + x.M)); } } } } INT o = -1; if (tmin[n - 1] != INT.MaxValue) { o = tmin[n - 1]; } IO.W(o); IO.F(); } } public class QUEUE<T> { protected INT m; private INT s, e, c; private T[] q; public QUEUE(INT max) { m = max; q = new T[m]; CLEAR(); } public void CLEAR() { e = 0; s = 0; c = 0; } public INT SIZE() { return c; } public T TOP() { return q[s]; } public T POP() { T r = q[s++]; s %= m; c--; return r; } public virtual void PUSH(T v) { q[e++] = v; e %= m; c++; } public bool EMPTY() { return SIZE() == 0; } } public class IO { private const int WMAX = 1000; private StringBuilder SB = new StringBuilder(); private T R<T>(Func<STR, T> f) { return f(Console.ReadLine()); } private T[] R<T>(Func<STR, T> f, char c) { return S().Split(c).Select(f).ToArray(); } private T[] R<T>(Func<STR, T> f, INT l) { T[] r = new T[l]; for (INT i = 0; i < l; i++) { r[i] = R(f); } return r; } private T[][] R<T>(Func<STR, T> f, INT l, char c) { T[][] r = new T[l][]; for (INT i = 0; i < l; i++) { r[i] = R<T>(f, c); } return r; } private void W<T>(Func<T, STR> f, T v, bool lf = true) { SB.Append(f(v)); if (lf) { SB.Append('\n'); } if (SB.Length >= WMAX) { F(); } } public STR S() { return R(s => s); } public STR[] S(char c) { return R(s => s, c); } public STR[] S(INT l) { return R(s => s, l); } public STR[][] S(INT l, char c) { return R(s => s, l, c); } public INT I() { return R(INT.Parse); } public INT[] I(char c) { return R(INT.Parse, c); } public INT[] I(INT l) { return R(INT.Parse, l); } public INT[][] I(INT l, char c) { return R(INT.Parse, l, c); } public DEC D() { return R(DEC.Parse); } public DEC[] D(char c) { return R(DEC.Parse, c); } public DEC[] D(INT l) { return R(DEC.Parse, l); } public DEC[][] D(INT l, char c) { return R(DEC.Parse, l, c); } public void W(object s, bool lf = true) { W(v => v.ToString(), s, lf); } public void F() { Console.Write(SB); SB.Length = 0; } }