結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36 WA * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
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