結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー | 14番 |
提出日時 | 2016-12-18 02:12:07 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,438 bytes |
コンパイル時間 | 3,037 ms |
コンパイル使用メモリ | 109,544 KB |
実行使用メモリ | 104,936 KB |
最終ジャッジ日時 | 2023-08-21 00:25:28 |
合計ジャッジ時間 | 9,537 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
28,328 KB |
testcase_01 | AC | 68 ms
21,956 KB |
testcase_02 | AC | 69 ms
19,872 KB |
testcase_03 | AC | 68 ms
20,004 KB |
testcase_04 | AC | 67 ms
19,776 KB |
testcase_05 | AC | 69 ms
22,012 KB |
testcase_06 | AC | 69 ms
21,904 KB |
testcase_07 | WA | - |
testcase_08 | AC | 70 ms
23,976 KB |
testcase_09 | AC | 70 ms
24,044 KB |
testcase_10 | AC | 70 ms
22,012 KB |
testcase_11 | AC | 70 ms
23,956 KB |
testcase_12 | AC | 70 ms
21,900 KB |
testcase_13 | AC | 69 ms
19,948 KB |
testcase_14 | AC | 94 ms
26,700 KB |
testcase_15 | AC | 93 ms
28,552 KB |
testcase_16 | AC | 94 ms
28,576 KB |
testcase_17 | WA | - |
testcase_18 | AC | 96 ms
26,592 KB |
testcase_19 | AC | 93 ms
28,556 KB |
testcase_20 | AC | 92 ms
26,472 KB |
testcase_21 | AC | 91 ms
28,472 KB |
testcase_22 | AC | 90 ms
26,408 KB |
testcase_23 | AC | 89 ms
26,460 KB |
testcase_24 | TLE | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
コンパイルメッセージ
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.Collections.Generic; using System.Text; public class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray(); this.MemberCount = inpt[0]; this.PathCount = inpt[1]; this.maxCost = new long[this.MemberCount]; this.minCost.Add(0,0); for(int i=0; i<this.PathCount; i++) { inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray(); if(!this.PathDic.ContainsKey(inpt[0])) { this.PathDic.Add(inpt[0], new Dictionary<int, int>()); } this.PathDic[inpt[0]].Add(inpt[1], inpt[2]); if(!this.PathRev.ContainsKey(inpt[1])) { this.PathRev.Add(inpt[1], new Dictionary<int, int>()); } this.PathRev[inpt[1]].Add(inpt[0], inpt[2]); } Queue<int> que = new Queue<int>(); que.Enqueue(0); while(que.Count > 0) { int cur = que.Dequeue(); long step = this.minCost[cur]; if(cur == this.MemberCount - 1) { continue; } this.PathDic[cur].ToList().ForEach(nv=>{ long nextStep = step + nv.Value; if(minCost.ContainsKey(nv.Key) && minCost[nv.Key] >= nextStep) { } else { minCost[nv.Key] = nextStep; que.Enqueue(nv.Key); } }); } this.maxCost[this.MemberCount-1] = minCost[this.MemberCount-1]; que.Enqueue(this.MemberCount-1); while(que.Count > 0) { int cur = que.Dequeue(); long step = this.maxCost[cur]; foreach(KeyValuePair<int,int> item in this.PathRev[cur]) { long nextStep = step-item.Value; if(item.Key == 0) { continue; } if(this.maxCost[item.Key] == 0 || maxCost[item.Key] > nextStep) { this.maxCost[item.Key] = nextStep; que.Enqueue(item.Key); } } } string ans = minCost[this.MemberCount-1] + " " + minCost.Count(a=>a.Value != maxCost[a.Key]) + "/" + this.MemberCount; Console.WriteLine(ans); } private Dictionary<int, Dictionary<int, int>> PathDic = new Dictionary<int, Dictionary<int, int>>(); private Dictionary<int, Dictionary<int, int>> PathRev = new Dictionary<int, Dictionary<int, int>>(); private Dictionary<int, long> minCost = new Dictionary<int, long>(); private long[] maxCost; private int MemberCount; private int PathCount; public class Reader { public static bool IsDebug = true; private static System.IO.StringReader SReader; private static string InitText = @" 8 12 0 1 3 0 2 3 1 3 3 1 4 3 2 3 3 2 4 3 3 5 3 3 6 3 4 5 3 4 6 3 5 7 3 6 7 3 "; public static string ReadLine() { if(IsDebug) { if(SReader == null) { SReader = new System.IO.StringReader(InitText.Trim()); } return SReader.ReadLine(); } else { return Console.ReadLine(); } } } public static void Main(string[] args) { Program prg = new Program(); prg.Proc(); } }