No.1 道のショートカット

■■■問題■■■

N個の町があります。それぞれ1・・・Nと番号がふられています。
それぞれの街は直接、道でつながっているものもあれば、つながってないものがあります。
それぞれの道は、町Siから町Tiに行くのにYiのコスト(お金：円)がかかり、Mi単位時間かかります。

あなたは1の町にいます。
Nの都市に行きたいと思っています。
何個道や町を経由してもいいですが、あなたは今C円しか持っていません。
(つまり、通った道のコストYiの合計をC以下にしないといけない。)

その中で一番早く付く道を選べた時、合計の単位時間を答えてください。
この制約の中で辿りつけない場合-1を返してください。

■■■入力■■■

N
C
V
S1 S2 S3 ・・・ SV
T1 T2 T3 ・・・ TV
Y1 Y2 Y3 ・・・ YV
M1 M2 M3 ・・・ MV

1行目に、町の数を表す整数 N (1 <= N <= 50) が与えられる。
2行目に、手持ちのお金を表す整数 C (0 <= C <= 300) が与えられる。
3行目に、道の数を表す整数 V (1 <= V <= 1500) が与えられる。
4行目に、Si (1  <= Si < N)がV個スペース区切りで与えられる。
5行目に、Ti (Si <  Ti <= N)がV個スペース区切りで与えられる。
6行目に、Yi (1  <= Yi <= C)がV個スペース区切りで与えられる。
7行目に、Mi (1  <= Mi <= 1000)がV個スペース区切りで与えられる。

Si,Ti,Yi,Mi は それぞれiインデックスで町 Si → 町Ti (有向グラフ)の移動に
コストYiがかかり、Mi単位時間かかるという意味です。

制約的につまり、町どうしを道でつないだ後にできるグラフは閉路（ループ）がないとし、
番号的には　Si < Tiとなっているとする。
つまり、番号的に戻る経路(例えば町3から町1など)へは考えなくてもよい。
道の接続的に町Nに辿りつけない場合もあります。

■■■出力■■■

1の町からNの町へ行く一番早く付く道を選べた時、合計の単位時間を答えてください。
この制約の中で辿りつけない場合-1を返してください。
最後に改行してください。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("100");
            WillReturn.Add("3");
            WillReturn.Add("1 2 1");
            WillReturn.Add("2 3 3");
            WillReturn.Add("10 90 10");
            WillReturn.Add("10 10 50");
            //20
            //1→3 と行くと コスト10だが、単位時間が50掛かる。
            //1→2→3 と行くと 一文無しになるが、20単位時間なので早いのでこちらを選択する。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("100");
            WillReturn.Add("3");
            WillReturn.Add("1 2 1");
            WillReturn.Add("2 3 3");
            WillReturn.Add("1 100 10");
            WillReturn.Add("10 10 50");
            //50
            //1→2→3 と行くと時間は20と短いが、コスト101かかるため選択できない。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("19");
            WillReturn.Add("1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9");
            WillReturn.Add("3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10");
            WillReturn.Add("8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6");
            WillReturn.Add("8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrPos;
        internal int SumC;
        internal int SumM;
        internal string Path;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        int C = int.Parse(InputList[1]);
        int[] SArr = InputList[3].Split(' ').Select(X => int.Parse(X)).ToArray();
        int[] TArr = InputList[4].Split(' ').Select(X => int.Parse(X)).ToArray();
        int[] YArr = InputList[5].Split(' ').Select(X => int.Parse(X)).ToArray();
        int[] MArr = InputList[6].Split(' ').Select(X => int.Parse(X)).ToArray();
        int UB = SArr.GetUpperBound(0);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrPos = 1;
        WillPush.SumC = WillPush.SumM = 0;
        WillPush.Path = "1";
        stk.Push(WillPush);

        //SumM[SumC]なDictの配列(ノード番号を添字とする)
        var MemoDictArr = new Dictionary<int, int>[N + 1];
        for (int I = 1; I <= N; I++) {
            MemoDictArr[I] = new Dictionary<int, int>();
        }

        bool HasAnswer = false;
        string AnswerPath = "";
        int AnswerSumM = int.MaxValue;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア処理
            if (Popped.CurrPos == N) {
                HasAnswer = true;
                if (AnswerSumM > Popped.SumM) {
                    AnswerSumM = Popped.SumM;
                    AnswerPath = Popped.Path;
                    Console.WriteLine("解候補{0}を発見", Popped.Path);
                }
                continue;
            }

            for (int I = 0; I <= UB; I++) {
                if (Popped.CurrPos != SArr[I]) continue;
                WillPush.CurrPos = TArr[I];
                WillPush.SumC = Popped.SumC + YArr[I];
                WillPush.SumM = Popped.SumM + MArr[I];
                WillPush.Path = Popped.Path + string.Format(",{0}", TArr[I]);

                if (WillPush.SumC > C) continue;

                if (MemoDictArr[WillPush.CurrPos].ContainsKey(WillPush.SumC)) {
                    if (MemoDictArr[WillPush.CurrPos][WillPush.SumC]
                        < WillPush.SumM) {
                        continue;
                    }
                }
                MemoDictArr[WillPush.CurrPos][WillPush.SumC] = WillPush.SumM;

                stk.Push(WillPush);
            }
        }
        if (HasAnswer) {
            Console.WriteLine(new string('■', 15));
            Console.WriteLine("解を発見");
            Console.WriteLine(AnswerSumM);
            Console.WriteLine("経路は{0}", AnswerPath);
        }
        else Console.WriteLine(-1);
    }
}

デバッグ情報付の実行結果

解候補1,3を発見
解候補1,2,3を発見
■■■■■■■■■■■■■■■
解を発見
20
経路は1,2,3

解説

Dictの配列に、そのノードまでのコスト合計と時間合計をメモする
深さ優先探索で解いてます。