#183767 (C#(csc)) No.1 道のショートカット

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	バカらっく
提出日時	2017-06-25 12:04:18
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	86 ms / 5,000 ms
コード長	6,663 bytes
コンパイル時間	2,454 ms
コンパイル使用メモリ	111,568 KB
実行使用メモリ	26,340 KB
最終ジャッジ日時	2023-09-27 22:09:07
合計ジャッジ時間	7,569 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	72 ms 21,824 KB
testcase_01	AC	73 ms 23,824 KB
testcase_02	AC	72 ms 21,924 KB
testcase_03	AC	72 ms 23,916 KB
testcase_04	AC	72 ms 21,876 KB
testcase_05	AC	73 ms 23,844 KB
testcase_06	AC	73 ms 23,912 KB
testcase_07	AC	73 ms 21,784 KB
testcase_08	AC	84 ms 22,260 KB
testcase_09	AC	82 ms 20,008 KB
testcase_10	AC	83 ms 24,000 KB
testcase_11	AC	85 ms 24,136 KB
testcase_12	AC	85 ms 22,220 KB
testcase_13	AC	85 ms 22,148 KB
testcase_14	AC	75 ms 21,780 KB
testcase_15	AC	70 ms 21,752 KB
testcase_16	AC	82 ms 22,024 KB
testcase_17	AC	73 ms 23,848 KB
testcase_18	AC	75 ms 21,856 KB
testcase_19	AC	74 ms 21,776 KB
testcase_20	AC	82 ms 24,060 KB
testcase_21	AC	82 ms 21,904 KB
testcase_22	AC	74 ms 23,896 KB
testcase_23	AC	85 ms 26,144 KB
testcase_24	AC	84 ms 21,972 KB
testcase_25	AC	81 ms 23,996 KB
testcase_26	AC	81 ms 23,996 KB
testcase_27	AC	86 ms 26,340 KB
testcase_28	AC	72 ms 19,828 KB
testcase_29	AC	85 ms 22,120 KB
testcase_30	AC	82 ms 22,028 KB
testcase_31	AC	82 ms 21,976 KB
testcase_32	AC	83 ms 24,116 KB
testcase_33	AC	83 ms 19,912 KB
testcase_34	AC	84 ms 24,164 KB
testcase_35	AC	82 ms 22,188 KB
testcase_36	AC	83 ms 22,032 KB
testcase_37	AC	83 ms 24,172 KB
testcase_38	AC	73 ms 21,744 KB
testcase_39	AC	85 ms 23,976 KB
testcase_40	AC	82 ms 19,956 KB
testcase_41	AC	81 ms 24,048 KB
testcase_42	AC	74 ms 21,772 KB
testcase_43	AC	70 ms 21,828 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

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();
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード