結果

問題 No.1 道のショートカット
ユーザー バカらっくバカらっく
提出日時 2017-06-25 11:58:46
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,412 bytes
コンパイル時間 2,435 ms
コンパイル使用メモリ 111,788 KB
実行使用メモリ 28,460 KB
最終ジャッジ日時 2023-09-22 13:12:54
合計ジャッジ時間 7,499 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
21,856 KB
testcase_01 AC 70 ms
21,872 KB
testcase_02 AC 69 ms
21,828 KB
testcase_03 AC 72 ms
21,804 KB
testcase_04 AC 70 ms
21,836 KB
testcase_05 AC 71 ms
23,868 KB
testcase_06 AC 71 ms
23,780 KB
testcase_07 AC 73 ms
23,892 KB
testcase_08 AC 85 ms
24,124 KB
testcase_09 AC 83 ms
24,076 KB
testcase_10 AC 87 ms
23,984 KB
testcase_11 AC 92 ms
26,140 KB
testcase_12 AC 94 ms
28,460 KB
testcase_13 AC 94 ms
28,340 KB
testcase_14 AC 75 ms
23,904 KB
testcase_15 AC 70 ms
23,852 KB
testcase_16 WA -
testcase_17 AC 71 ms
21,936 KB
testcase_18 AC 75 ms
21,752 KB
testcase_19 AC 74 ms
23,828 KB
testcase_20 AC 80 ms
22,004 KB
testcase_21 WA -
testcase_22 AC 72 ms
21,716 KB
testcase_23 AC 90 ms
28,116 KB
testcase_24 AC 86 ms
28,160 KB
testcase_25 AC 81 ms
22,008 KB
testcase_26 AC 84 ms
22,012 KB
testcase_27 AC 95 ms
26,216 KB
testcase_28 AC 73 ms
21,852 KB
testcase_29 AC 90 ms
28,264 KB
testcase_30 AC 83 ms
21,960 KB
testcase_31 AC 81 ms
21,948 KB
testcase_32 AC 84 ms
23,968 KB
testcase_33 AC 83 ms
19,896 KB
testcase_34 AC 92 ms
28,288 KB
testcase_35 AC 82 ms
22,124 KB
testcase_36 AC 89 ms
25,992 KB
testcase_37 WA -
testcase_38 AC 74 ms
21,844 KB
testcase_39 WA -
testcase_40 AC 82 ms
22,124 KB
testcase_41 AC 81 ms
21,932 KB
testcase_42 AC 73 ms
21,740 KB
testcase_43 AC 70 ms
21,732 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 = @"




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