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

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	バカらっく
提出日時	2017-06-25 11:52:49
言語	C#(csc) (csc 3.9.0)
結果	RE
実行時間	-
コード長	14,819 bytes
コンパイル時間	1,152 ms
コンパイル使用メモリ	111,232 KB
実行使用メモリ	24,368 KB
最終ジャッジ日時	2024-07-08 04:55:58
合計ジャッジ時間	4,366 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	34 ms 19,456 KB
testcase_01	AC	33 ms 19,456 KB
testcase_02	AC	33 ms 19,456 KB
testcase_03	AC	32 ms 19,200 KB
testcase_04	AC	33 ms 19,328 KB
testcase_05	AC	33 ms 19,200 KB
testcase_06	AC	34 ms 19,456 KB
testcase_07	AC	34 ms 19,584 KB
testcase_08	AC	43 ms 23,168 KB
testcase_09	AC	42 ms 22,144 KB
testcase_10	AC	44 ms 23,296 KB
testcase_11	AC	48 ms 23,960 KB
testcase_12	AC	48 ms 24,368 KB
testcase_13	AC	48 ms 24,192 KB
testcase_14	AC	33 ms 19,584 KB
testcase_15	RE	-
testcase_16	WA	-
testcase_17	AC	33 ms 19,456 KB
testcase_18	AC	34 ms 19,456 KB
testcase_19	AC	34 ms 19,840 KB
testcase_20	AC	39 ms 20,864 KB
testcase_21	WA	-
testcase_22	AC	33 ms 19,584 KB
testcase_23	AC	47 ms 23,600 KB
testcase_24	AC	43 ms 24,028 KB
testcase_25	AC	39 ms 20,992 KB
testcase_26	AC	38 ms 20,864 KB
testcase_27	AC	50 ms 23,956 KB
testcase_28	AC	34 ms 19,584 KB
testcase_29	AC	48 ms 24,056 KB
testcase_30	AC	38 ms 20,608 KB
testcase_31	AC	41 ms 22,912 KB
testcase_32	AC	43 ms 22,400 KB
testcase_33	AC	41 ms 21,632 KB
testcase_34	AC	46 ms 24,060 KB
testcase_35	AC	39 ms 20,480 KB
testcase_36	AC	42 ms 22,016 KB
testcase_37	WA	-
testcase_38	AC	34 ms 19,456 KB
testcase_39	WA	-
testcase_40	AC	39 ms 20,480 KB
testcase_41	AC	38 ms 19,584 KB
testcase_42	AC	33 ms 19,584 KB
testcase_43	RE	-

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

コンパイルメッセージ

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;
            }
            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 = @"




50
223
800
30 4 15 16 8 4 33 5 9 15 27 30 35 1 4 16 4 35 28 6 3 7 12 6 39 27 25 20 4 20 12 15 9 24 25 7 33 11 26 13 6 5 1 11 30 12 12 11 6 8 30 12 39 4 8 39 10 39 8 2 6 17 28 3 38 20 6 10 4 3 2 4 7 9 13 28 1 2 15 44 9 9 8 36 14 2 29 37 3 20 30 17 19 21 22 12 9 11 7 8 28 26 13 13 9 8 1 37 13 18 19 4 3 26 14 11 1 7 8 18 10 28 22 23 42 13 38 1 12 18 22 9 21 33 5 26 28 26 34 6 12 10 14 4 27 33 19 32 4 8 22 16 21 7 28 36 5 9 17 3 24 10 43 15 27 28 4 9 19 23 8 1 36 20 14 21 9 9 8 15 7 2 28 32 31 26 1 20 20 7 4 8 9 11 13 11 6 15 18 9 6 6 5 8 29 43 43 7 3 12 2 4 6 15 27 12 13 5 6 33 6 29 36 1 7 1 24 6 14 40 17 26 24 28 17 3 3 39 2 19 3 13 3 2 17 15 1 8 12 23 12 7 21 29 25 8 11 11 36 6 13 34 29 34 24 25 32 2 6 5 33 11 13 8 13 34 18 31 14 10 29 17 3 7 16 12 13 33 30 6 26 29 12 28 34 19 18 18 3 27 14 6 16 10 7 20 18 17 21 22 35 33 30 31 18 14 1 15 12 1 14 8 17 2 2 28 9 28 33 3 42 7 7 3 36 11 9 27 22 27 12 35 30 19 23 23 3 3 3 38 38 3 27 24 22 14 8 23 20 17 3 46 20 7 10 17 21 13 25 3 14 14 11 9 15 9 34 20 5 7 24 17 21 24 9 13 18 23 2 6 22 21 10 15 12 14 16 15 12 32 11 3 27 3 11 11 21 24 9 42 2 13 6 9 47 15 6 7 22 14 21 6 46 16 26 29 10 21 13 9 19 9 18 10 33 14 27 10 35 23 6 43 15 31 21 5 14 2 40 26 24 38 16 29 16 11 40 23 6 12 8 16 16 2 2 3 25 1 13 18 17 7 11 2 22 18 24 28 16 7 6 11 12 17 29 25 3 20 46 17 7 2 1 34 10 17 9 33 34 36 9 2 7 34 34 4 12 7 26 6 18 22 2 9 6 7 29 36 3 15 2 9 11 14 41 1 8 27 38 11 7 18 4 14 11 18 12 36 23 23 27 16 41 10 14 5 19 49 7 13 28 22 9 19 19 37 31 28 16 31 9 17 20 26 10 13 31 6 25 14 12 12 2 17 19 20 30 10 2 18 10 20 23 4 47 27 17 32 21 7 44 8 7 4 13 9 42 19 16 30 6 9 8 10 7 38 35 12 5 20 41 24 12 29 3 3 39 27 2 27 41 8 33 26 23 5 5 7 3 9 13 29 34 20 1 10 15 16 6 20 15 23 4 5 21 4 8 6 27 40 13 11 16 2 31 19 6 33 15 12 10 13 39 20 20 12 5 1 9 12 34 20 19 3 6 2 3 4 43 21 27 2 2 13 19 19 3 22 4 1 13 42 28 22 32 25 42 18 11 32 4 21 37 4 2 27 22 31 29 12 4 28 47 17 8 3 28 23 41 13 10 43 39 24 2 30 16 9 3 38 10 43 16 14 3 46 23 15 5 13 20 14 1 26 3 13 13 27 20 2 18 15 42 35 19 25 45 21 36 3 7 4 1 8 23 27 19 36 2 11 5 17 14 24 7 11 14 12 20 36 29 9 3 44 5 4 14 2 29 8 26 23 2 1 11 9 25 7 20 33
42 15 30 26 49 41 43 40 34 43 48 47 50 9 34 35 28 38 48 14 25 37 21 34 42 38 36 38 7 29 17 41 49 36 49 47 40 45 36 34 9 16 42 41 31 35 31 26 7 39 49 50 44 27 50 40 26 40 36 43 24 50 29 7 40 45 34 35 31 19 34 12 39 14 45 49 48 19 17 50 44 28 36 40 30 20 30 42 19 50 50 33 40 42 31 17 18 46 15 18 50 35 14 45 47 47 11 43 21 28 24 29 37 39 22 29 12 35 22 25 35 43 43 48 48 45 46 39 13 25 32 10 46 43 34 30 50 47 49 30 38 26 24 12 32 42 35 42 42 28 24 21 35 31 49 45 21 26 25 15 43 34 45 35 44 31 16 18 24 25 17 9 43 42 26 23 10 43 26 25 36 42 34 41 41 48 48 47 25 28 5 27 16 42 44 25 47 48 45 45 10 40 15 20 36 44 49 29 47 23 32 42 18 26 44 27 18 31 22 39 37 41 46 36 49 25 43 40 35 42 43 38 38 36 22 36 45 41 24 26 9 49 25 13 33 36 33 17 40 35 26 44 24 47 28 22 33 26 44 28 35 38 43 49 40 32 48 31 9 29 44 38 14 26 29 40 38 39 36 48 46 21 31 27 25 44 39 42 42 50 29 42 41 34 37 37 29 22 9 44 39 22 44 22 28 33 29 45 27 39 47 50 42 33 32 21 19 48 43 9 47 47 21 15 3 38 24 37 46 38 44 47 44 50 50 16 39 32 39 30 14 48 35 33 49 49 26 26 20 49 41 19 35 39 38 24 19 26 29 43 24 47 33 15 18 31 35 42 45 36 15 47 42 17 50 35 45 27 19 39 30 45 38 48 45 50 37 45 22 28 33 50 27 50 25 28 38 26 39 45 45 27 50 6 33 43 40 27 29 43 40 49 28 43 50 18 32 13 30 20 46 42 48 33 45 40 15 31 35 38 24 42 20 31 47 19 34 24 44 40 25 45 34 38 48 44 49 31 44 37 26 41 34 46 35 43 48 26 29 41 9 34 24 44 46 26 36 46 35 31 31 37 35 30 29 37 29 50 43 12 42 14 50 36 34 31 28 47 48 28 32 44 5 37 34 27 44 37 47 39 34 46 42 48 38 36 28 40 37 32 39 44 34 23 25 14 45 45 36 39 49 43 48 34 43 30 38 34 50 12 15 29 12 27 40 33 18 50 32 27 49 46 43 30 23 11 38 50 20 26 29 38 35 39 44 48 45 33 25 43 49 30 34 29 35 35 48 47 29 15 38 41 11 32 44 22 46 21 7 28 15 38 42 47 48 31 44 42 45 29 49 43 18 43 15 11 49 34 37 50 50 49 44 31 45 44 49 49 39 27 50 30 34 31 42 32 40 32 9 40 49 28 34 37 37 27 37 31 13 15 14 44 36 47 32 24 33 26 50 35 21 30 43 11 26 22 32 10 38 48 40 43 25 12 33 38 30 40 50 29 19 36 43 34 38 42 32 18 44 43 36 28 43 30 49 48 31 14 49 32 36 41 8 48 26 43 34 47 45 16 40 45 43 48 45 32 49 19 37 37 46 30 43 49 27 50 43 50 43 40 37 40 49 29 42 14 41 44 50 39 37 48 40 48 32 32 43 20 20 50 38 46 31 33 15 48 34 40 18 34 47 20 20 48 12 18 25 39 44 27 32 44 45 46 41 30 49 42 38 26 33 24 49 25 50 32 26 38 10 22 17 23 43 41 25 44 35 13 43 49 32 23 9 48 23 6 33 42 31 28 44 30 5 50 41 14 35 33 39 44
145 189 183 124 11 163 195 134 173 113 159 17 119 221 30 131 166 141 35 9 191 51 56 141 37 189 181 127 129 77 167 187 87 170 17 153 159 92 139 179 51 15 119 15 83 159 18 161 27 166 123 92 105 70 102 20 163 102 116 37 146 213 132 60 120 188 129 42 198 94 208 62 207 201 223 47 146 28 165 21 58 94 91 160 40 54 103 73 64 140 151 37 206 150 7 140 138 19 113 142 136 133 80 203 42 206 82 125 144 45 10 102 199 12 78 125 198 149 118 30 76 202 186 152 82 118 118 165 109 111 68 208 97 147 50 70 202 179 179 40 120 125 104 178 135 49 35 69 179 81 81 177 89 168 95 93 125 220 176 185 100 5 71 85 131 114 44 176 168 135 119 100 75 25 72 47 145 101 107 174 8 109 119 192 109 116 128 58 94 31 185 42 100 11 42 128 37 78 200 3 82 44 178 185 185 132 101 93 207 169 223 189 134 14 32 141 19 10 123 203 164 156 174 31 117 152 219 203 2 54 117 189 187 22 26 142 50 141 191 176 147 40 129 78 188 132 1 216 109 35 116 4 77 175 111 149 194 83 51 108 125 171 18 121 27 88 158 218 23 152 203 32 204 105 84 152 145 23 33 204 168 168 66 51 46 141 109 88 25 190 150 76 40 133 128 185 2 39 122 220 159 191 144 98 213 183 166 23 30 184 179 175 137 20 190 185 207 21 57 189 66 75 5 114 146 130 105 186 55 64 4 107 148 183 13 34 177 123 26 219 117 46 97 66 93 65 194 136 55 42 191 56 99 111 47 212 132 27 104 134 54 189 185 141 158 82 222 163 54 157 69 132 93 98 24 104 15 23 136 89 156 62 221 142 7 179 151 124 17 56 10 173 217 135 175 198 148 58 195 221 172 79 22 110 47 221 47 116 195 22 179 54 89 215 132 184 141 164 38 34 108 32 65 212 79 169 186 195 93 135 182 44 15 221 204 204 74 219 108 22 129 219 133 169 11 88 46 12 161 191 110 138 141 191 146 188 6 188 112 95 108 104 50 27 163 130 204 190 138 84 95 198 175 63 113 106 102 72 56 177 69 35 100 187 19 102 176 141 105 187 180 16 191 162 117 137 101 20 214 171 38 48 168 105 76 196 198 48 176 81 200 210 124 41 100 108 142 105 38 106 150 133 155 81 69 94 216 53 217 161 129 137 58 211 81 217 99 63 213 143 162 207 86 126 2 143 16 131 166 132 223 219 211 185 83 96 21 158 84 60 124 173 145 94 73 70 123 100 16 118 215 169 151 108 8 110 35 103 30 218 175 191 70 76 171 132 29 152 130 39 57 101 90 31 100 108 221 195 160 45 119 179 183 206 56 170 76 175 106 207 37 93 223 112 29 56 102 75 112 128 6 7 5 33 171 109 159 27 144 190 85 58 194 15 162 16 17 50 39 159 216 141 136 217 172 59 206 200 118 49 68 198 164 209 46 18 66 150 206 134 135 125 25 142 162 74 161 195 24 105 153 150 4 147 155 184 188 130 37 180 26 120 58 193 155 30 35 70 97 25 181 72 3 43 27 128 165 115 165 20 57 152 187 53 174 10 164 12 26 158 166 172 175 187 218 209 185 139 192 216 102 209 198 213 189 147 63 77 33 17 141 171 215 222 176 209 203 199 131 127 107 19 84 24 150 82 57 157 130 123 27 175 185 76 160 166 88 20 171 127 218 80 3 171 3 150 94 132 13 157 158 219 34 156 36 200 182 131 151 160 11 130 171 72 129 114 203 37 210 211 179 200 35 139 59 182 117 56 63 117
860 353 609 234 812 391 194 75 732 597 410 952 894 129 597 940 780 73 476 327 845 422 700 874 617 658 998 766 858 541 895 531 823 631 369 736 590 250 589 266 545 708 821 195 592 150 379 456 278 955 676 324 54 900 845 955 46 406 363 637 515 943 653 519 970 726 410 576 105 13 590 3 813 497 159 550 937 403 931 147 861 888 957 736 624 506 607 387 232 621 559 877 937 357 852 520 226 429 994 344 839 64 721 593 47 836 359 575 112 907 927 522 125 637 16 558 928 574 28 676 864 267 819 837 187 765 492 767 265 614 676 468 829 244 351 550 998 233 488 262 344 957 929 905 459 498 248 563 619 164 455 144 412 205 470 345 331 323 629 930 308 159 393 892 534 736 24 855 598 475 399 294 403 808 987 661 581 770 224 71 372 625 265 747 766 299 404 705 508 461 185 510 633 462 204 894 219 120 468 780 199 253 320 843 877 230 608 513 821 400 747 22 669 136 388 905 350 569 106 881 166 323 576 769 106 259 469 499 745 439 16 529 686 389 167 958 284 161 839 434 465 305 472 366 939 340 2 87 458 914 184 336 502 182 562 517 524 251 78 566 773 436 202 410 140 253 399 459 950 786 925 19 228 855 744 751 511 440 573 709 270 905 104 154 969 534 269 231 303 828 5 24 757 575 469 189 39 593 259 344 62 687 976 833 121 924 349 298 79 222 974 313 702 178 356 315 197 84 520 459 331 342 241 365 794 934 894 268 468 789 217 141 873 472 973 269 750 945 12 500 275 991 195 828 252 483 678 655 105 333 620 813 552 432 384 637 581 793 502 305 110 83 10 220 634 889 305 563 351 819 355 968 443 561 272 541 298 671 908 932 404 674 649 104 963 452 316 258 80 856 834 315 746 71 101 375 333 314 979 469 701 376 266 848 785 634 11 15 298 170 202 485 381 212 899 484 20 834 402 392 325 909 229 506 65 760 66 727 389 111 709 1000 136 501 814 995 447 967 763 902 739 187 842 684 648 244 47 148 915 117 58 531 334 577 620 729 132 214 72 932 762 650 704 195 823 993 1 524 626 322 756 544 206 854 265 212 689 838 24 241 558 496 793 687 116 642 254 919 442 350 907 713 934 286 986 634 223 398 108 969 757 687 263 813 986 580 857 352 66 544 697 856 8 311 302 539 746 711 393 321 66 687 288 43 492 839 941 363 917 363 422 365 478 896 85 926 251 460 5 262 256 765 501 878 29 104 844 747 567 116 597 941 52 282 106 990 941 601 991 852 35 938 761 904 779 251 868 138 689 323 76 797 766 844 327 632 357 933 241 505 411 290 682 519 507 983 203 811 787 837 840 121 362 479 553 982 470 529 559 320 709 511 716 279 281 909 847 740 715 400 960 716 49 701 507 728 395 329 617 808 625 799 46 498 552 529 898 180 821 327 800 46 443 617 28 257 414 729 485 69 704 911 763 404 898 330 481 949 500 113 442 618 243 89 838 435 461 904 835 963 407 20 485 871 385 886 174 550 267 892 954 424 793 770 212 850 205 784 51 751 268 184 162 55 525 891 866 286 654 88 128 168 325 166 373 109 240 720 377 591 435 352 336 364 246 978 202 640 234 534 912 147 946 508 797 445 526 260 280 327 365 810 702 332 484 682 148 297 294 812 478 358 683 779 648 574 870 995 59 882 909 441 175 558 653 736 863 535 114 717 662 409 333 909 631 722 890 22 270 248 365 413 928 971 755 374 27 333 592 109 730 66 990 451 204 976 442 461 931 304 356 632 224 430 933 732 385 753 36 410 312 685 929 645 690 181 143 135 329 3




";
	}

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード