結果

問題 No.1 道のショートカット
ユーザー バカらっくバカらっく
提出日時 2017-06-25 12:04:18
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 49 ms / 5,000 ms
コード長 6,663 bytes
コンパイル時間 4,047 ms
コンパイル使用メモリ 110,336 KB
実行使用メモリ 22,400 KB
最終ジャッジ日時 2024-07-20 16:32:23
合計ジャッジ時間 3,885 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
19,328 KB
testcase_01 AC 36 ms
19,200 KB
testcase_02 AC 35 ms
19,328 KB
testcase_03 AC 36 ms
19,072 KB
testcase_04 AC 36 ms
19,328 KB
testcase_05 AC 36 ms
19,072 KB
testcase_06 AC 36 ms
19,072 KB
testcase_07 AC 38 ms
19,200 KB
testcase_08 AC 44 ms
20,480 KB
testcase_09 AC 43 ms
20,224 KB
testcase_10 AC 43 ms
20,480 KB
testcase_11 AC 45 ms
21,632 KB
testcase_12 AC 46 ms
21,632 KB
testcase_13 AC 45 ms
21,120 KB
testcase_14 AC 38 ms
19,584 KB
testcase_15 AC 35 ms
19,200 KB
testcase_16 AC 42 ms
19,584 KB
testcase_17 AC 36 ms
19,200 KB
testcase_18 AC 37 ms
19,328 KB
testcase_19 AC 39 ms
19,328 KB
testcase_20 AC 43 ms
19,968 KB
testcase_21 AC 42 ms
19,712 KB
testcase_22 AC 38 ms
19,328 KB
testcase_23 AC 46 ms
22,400 KB
testcase_24 AC 45 ms
21,248 KB
testcase_25 AC 42 ms
19,840 KB
testcase_26 AC 43 ms
19,712 KB
testcase_27 AC 49 ms
21,760 KB
testcase_28 AC 37 ms
19,328 KB
testcase_29 AC 46 ms
21,120 KB
testcase_30 AC 44 ms
19,840 KB
testcase_31 AC 44 ms
20,864 KB
testcase_32 AC 44 ms
20,224 KB
testcase_33 AC 43 ms
20,096 KB
testcase_34 AC 45 ms
21,760 KB
testcase_35 AC 42 ms
20,096 KB
testcase_36 AC 43 ms
20,352 KB
testcase_37 AC 44 ms
20,608 KB
testcase_38 AC 38 ms
19,456 KB
testcase_39 AC 42 ms
19,584 KB
testcase_40 AC 41 ms
19,840 KB
testcase_41 AC 42 ms
19,584 KB
testcase_42 AC 36 ms
19,200 KB
testcase_43 AC 35 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.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int cityCount = int.Parse(Reader.ReadLine());
        int moneyAmount = int.Parse(Reader.ReadLine());
        int roadCount = int.Parse(Reader.ReadLine());
        int[] fromList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)-1).ToArray();
        int[] toList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)-1).ToArray();
        int[] moneyCostList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        int[] timeCostList = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

        for (int i = 0; i < roadCount; i++){
            Road r = new Road(fromList[i], toList[i], moneyCostList[i], timeCostList[i]);
            if(!RoadList.ContainsKey(fromList[i])) {
                RoadList.Add(fromList[i], new Dictionary<int, List<Road>>());
            }
            if(!RoadList[fromList[i]].ContainsKey(toList[i])) {
                RoadList[fromList[i]].Add(toList[i], new List<Road>());
            }
            RoadList[fromList[i]][toList[i]].Add(r);
            /*
            if(!RoadList.ContainsKey(toList[i])) {
                RoadList.Add(toList[i], new Dictionary<int, List<Road>>());
            }
            if(!RoadList[toList[i]].ContainsKey(fromList[i])) {
                RoadList[toList[i]].Add(fromList[i], new List<Road>());
            }
            RoadList[toList[i]][fromList[i]].Add(r);
            */
        }
        MapState[] map = new MapState[cityCount];

        // 0 から CityCount-1 へ行く
        Queue<Task> q = new Queue<Task>();
        q.Enqueue(new Task(0,0));
        map[0] = new MapState();
        map[0].MoneyTime.Add(0, 0);
        while(q.Count()>0) {
            Task t = q.Dequeue();
            int time = map[t.City].MoneyTime[t.Money];

            if(t.City == cityCount-1) {
                continue;
            }
            if(!RoadList.ContainsKey(t.City)) {
                continue;
            }
            foreach(int nextCity in RoadList[t.City].Keys) {
                if(nextCity == 0) {
                    continue;
                }
                foreach(Road r in RoadList[t.City][nextCity]) {
					int nextTime = time + r.TimeCost;
					int nextMoney = t.Money + r.MoneyCost;
					if (nextMoney > moneyAmount)
					{
						continue;
					}
					if (map[nextCity] != null)
					{
						if (map[nextCity].MoneyTime.Any(a => a.Key <= nextMoney && a.Value <= nextTime))
						{
							continue;
						}
						if (map[nextCity].MoneyTime.ContainsKey(nextMoney) && map[nextCity].MoneyTime[nextMoney] <= nextTime)
						{
							continue;
						}
					}
					if (map[nextCity] == null)
					{
						map[nextCity] = new MapState();
					}
					map[nextCity].MoneyTime[nextMoney] = nextTime;
					q.Enqueue(new Task(nextCity, nextMoney));
				}
            }
        }
        int ans = -1;
        if(map[cityCount-1] !=null) {
            ans = map[cityCount - 1].MoneyTime.Min(a => a.Value);
        }
        Console.WriteLine(ans);
    }

    private class Task {
        public int City;
        public int Money;
        public Task(int c,int m) {
            this.City = c;
            this.Money = m;
        }
    }
    private class MapState {
        public Dictionary<int, int> MoneyTime = new Dictionary<int, int>();
    }

    private Dictionary<int, Dictionary<int, List<Road>>> RoadList = new Dictionary<int, Dictionary<int, List<Road>>>();

    private class Road {
        public int City1;
        public int City2;
        public int MoneyCost;
        public int TimeCost;
        public Road(int city1, int city2, int money, int time) {
            this.City1 = city1;
            this.City2 = city2;
            this.MoneyCost = money;
            this.TimeCost = time;
        }
    }

    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"





39
297
167
18 23 2 11 30 15 26 30 29 11 22 4 1 27 14 28 1 33 30 31 36 13 38 25 17 25 30 8 3 29 25 4 34 8 15 4 15 12 2 35 2 27 24 4 10 25 8 18 37 22 19 22 31 22 5 10 38 14 9 29 23 11 3 11 19 7 35 2 16 2 15 33 38 18 26 15 28 6 8 33 10 11 14 30 33 32 18 17 24 35 38 14 18 26 8 15 12 30 32 24 31 9 3 22 21 32 14 37 31 4 31 32 18 30 28 14 29 28 14 18 36 3 18 14 25 16 34 7 15 30 9 29 27 12 24 33 35 37 13 16 18 11 9 1 1 24 13 26 35 36 8 24 15 17 13 19 3 38 11 13 36 7 29 2 36 22 15
21 30 30 18 31 17 37 33 36 32 32 36 12 28 26 30 37 38 37 32 39 31 39 29 35 34 32 31 14 32 28 39 39 37 35 26 28 30 7 38 6 33 31 15 37 34 21 32 38 37 34 36 37 24 34 32 39 22 24 32 33 20 28 28 20 17 38 7 26 21 39 39 39 31 38 24 33 30 36 39 34 34 23 35 37 36 26 29 38 36 39 24 27 34 23 30 25 38 39 38 38 12 30 28 22 34 21 38 34 28 35 33 29 35 33 38 36 36 23 32 38 19 26 17 28 18 37 10 37 38 35 39 32 31 26 37 39 38 38 36 26 24 13 12 11 37 29 31 36 39 39 35 28 24 28 21 39 39 34 18 38 24 35 18 38 30 37
59 145 297 152 137 193 186 145 183 283 136 138 51 225 261 269 18 200 5 211 291 100 151 244 169 194 64 275 260 170 72 276 99 153 166 131 266 10 289 87 124 192 125 90 134 127 36 168 17 96 252 240 293 26 263 154 145 107 170 120 109 263 147 211 207 187 109 26 101 153 169 189 34 97 161 195 20 134 205 92 214 136 268 88 249 280 79 286 155 63 200 202 141 102 243 87 154 165 84 146 67 99 51 86 152 55 27 8 13 3 25 207 90 95 102 160 274 171 127 272 135 31 149 105 259 53 124 57 176 112 231 221 14 131 131 195 175 182 142 127 174 97 274 251 80 65 260 217 63 294 123 4 255 283 245 239 3 56 222 218 217 248 241 122 138 259 210
356 518 175 730 104 843 67 682 891 309 625 302 960 446 881 698 776 193 956 630 894 423 778 577 707 378 413 961 423 507 649 871 283 66 649 731 913 697 972 345 709 421 191 975 356 125 83 257 334 634 184 844 598 992 727 139 845 414 335 656 360 533 231 460 943 281 982 543 473 775 94 565 225 995 550 974 939 233 63 798 757 256 854 898 581 421 400 719 328 961 503 674 104 291 692 138 115 690 475 106 741 924 977 997 373 501 308 587 217 805 394 264 650 403 66 12 247 80 652 25 516 1 94 895 476 990 122 739 263 42 282 256 73 890 435 142 248 28 924 681 503 431 882 948 191 974 908 867 216 487 14 771 536 840 615 481 830 248 484 422 779 332 848 145 365 11 453







";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}
0