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

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	バカらっく
提出日時	2017-06-25 11:58:46
言語	C#(csc) (csc 3.9.0)
結果	WA
実行時間	-
コード長	4,412 bytes
コンパイル時間	974 ms
コンパイル使用メモリ	117,616 KB
実行使用メモリ	27,752 KB
最終ジャッジ日時	2024-07-08 04:56:02
合計ジャッジ時間	3,705 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	33 ms 19,456 KB
testcase_01	AC	34 ms 19,072 KB
testcase_02	AC	34 ms 19,200 KB
testcase_03	AC	32 ms 19,072 KB
testcase_04	AC	32 ms 19,072 KB
testcase_05	AC	33 ms 19,200 KB
testcase_06	AC	33 ms 19,456 KB
testcase_07	AC	32 ms 19,456 KB
testcase_08	AC	42 ms 22,912 KB
testcase_09	AC	41 ms 22,144 KB
testcase_10	AC	42 ms 23,424 KB
testcase_11	AC	48 ms 23,808 KB
testcase_12	AC	47 ms 23,936 KB
testcase_13	AC	49 ms 23,936 KB
testcase_14	AC	34 ms 19,584 KB
testcase_15	AC	31 ms 19,328 KB
testcase_16	WA	-
testcase_17	AC	32 ms 19,328 KB
testcase_18	AC	34 ms 19,840 KB
testcase_19	AC	34 ms 19,712 KB
testcase_20	AC	38 ms 20,352 KB
testcase_21	WA	-
testcase_22	AC	35 ms 19,456 KB
testcase_23	AC	44 ms 23,736 KB
testcase_24	AC	42 ms 23,664 KB
testcase_25	AC	38 ms 20,608 KB
testcase_26	AC	38 ms 20,224 KB
testcase_27	AC	51 ms 23,840 KB
testcase_28	AC	34 ms 19,328 KB
testcase_29	AC	45 ms 24,060 KB
testcase_30	AC	38 ms 20,480 KB
testcase_31	AC	38 ms 21,120 KB
testcase_32	AC	41 ms 22,144 KB
testcase_33	AC	40 ms 21,376 KB
testcase_34	AC	45 ms 23,728 KB
testcase_35	AC	38 ms 20,096 KB
testcase_36	AC	43 ms 22,272 KB
testcase_37	WA	-
testcase_38	AC	34 ms 19,328 KB
testcase_39	WA	-
testcase_40	AC	41 ms 20,224 KB
testcase_41	AC	41 ms 19,840 KB
testcase_42	AC	34 ms 19,584 KB
testcase_43	AC	31 ms 19,328 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 = @"




41
278
1
3
16
192
606







";
	}

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード