結果

問題 No.1 道のショートカット
ユーザー バカらっく
提出日時 2017-06-25 11:43:43
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 4,183 bytes
コンパイル時間 2,695 ms
コンパイル使用メモリ 112,420 KB
実行使用メモリ 27,388 KB
最終ジャッジ日時 2024-07-08 04:55:24
合計ジャッジ時間 5,727 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 RE * 1
other AC * 8 RE * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
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, Road>());
            }
            RoadList[fromList[i]].Add(toList[i], r);
            if(!RoadList.ContainsKey(toList[i])) {
                RoadList.Add(toList[i], new Dictionary<int, Road>());
            }
            RoadList[toList[i]].Add(fromList[i], 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;
                }
                int nextTime = time + RoadList[t.City][nextCity].TimeCost;
                int nextMoney = t.Money + RoadList[t.City][nextCity].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, Road>> RoadList = new Dictionary<int, Dictionary<int, 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 = @"




3
100
3
1 2 1
2 3 3
10 90 10
10 10 50



";
	}

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