ABC422-F Eat and Ride

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("5 6");
            WillReturn.Add("3 1 4 1 5");
            WillReturn.Add("1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("2 3");
            WillReturn.Add("2 4");
            WillReturn.Add("3 5");
            WillReturn.Add("4 5");
            //0
            //3
            //3
            //7
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 4");
            WillReturn.Add("1000000000 1000000000 1000000000 1000000000 1000000000");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            WillReturn.Add("4 5");
            //0
            //1000000000
            //3000000000
            //6000000000
            //10000000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 20");
            WillReturn.Add("74931 58277 33783 91022 53003 11085 65924 63548 78622 77307");
            WillReturn.Add("1 8");
            WillReturn.Add("3 6");
            WillReturn.Add("5 10");
            WillReturn.Add("4 6");
            WillReturn.Add("1 3");
            WillReturn.Add("1 7");
            WillReturn.Add("2 6");
            WillReturn.Add("7 10");
            WillReturn.Add("8 9");
            WillReturn.Add("3 4");
            WillReturn.Add("4 4");
            WillReturn.Add("4 6");
            WillReturn.Add("6 6");
            WillReturn.Add("5 10");
            WillReturn.Add("1 7");
            WillReturn.Add("4 5");
            WillReturn.Add("1 2");
            WillReturn.Add("3 7");
            WillReturn.Add("2 3");
            WillReturn.Add("5 8");
            //0
            //74931
            //74931
            //183645
            //213410
            //183645
            //74931
            //74931
            //213410
            //215786
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        int NodeCnt = (int)wkArr[0];

        long[] WeightArr = GetSplitArr(InputList[1]);

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            int FromNode = (int)wkArr[0];
            int ToNode = (int)wkArr[1];

            if (mToNodeListDict.ContainsKey(FromNode) == false) {
                mToNodeListDict[FromNode] = new List<int>();
            }
            if (mToNodeListDict.ContainsKey(ToNode) == false) {
                mToNodeListDict[ToNode] = new List<int>();
            }
            mToNodeListDict[FromNode].Add(ToNode);
            mToNodeListDict[ToNode].Add(FromNode);
        }

        // 最小コスト[残り移動回数 , ノード] なインラインDP表
        int UB0 = NodeCnt - 1;
        int UB1 = NodeCnt;

        long[,] DPArr = new long[UB0 + 1, UB1 + 1];

        for (int I = 0; I <= UB0; I++) {
            DPArr[I, 1] = 0;
            for (int J = 2; J <= UB1; J++) {
                DPArr[I, J] = long.MaxValue;
            }
        }

        // インラインDP
        for (int I = UB0; 1 <= I; I--) {
            for (int J = UB1; 1 <= J; J--) {
                if (DPArr[I, J] == long.MaxValue) continue;

                foreach (int EachToNode in mToNodeListDict[J]) {
                    int NewI = I - 1;
                    int NewJ = EachToNode;
                    long NewVal = DPArr[I, J] + WeightArr[J - 1] * I;

                    if (DPArr[NewI, NewJ] <= NewVal) {
                        continue;
                    }
                    DPArr[NewI, NewJ] = NewVal;
                }
            }
        }

        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= NodeCnt; I++) {
            sb.Append(DPArr[0, I]);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

解説

最小コスト[残り移動回数 ,現在ノード]な
二次元配列を考えます。

5|0 ? ? ? ? ? ? ? ?
4|0 ? ? ? ? ? ? ? ?
3|0 ? ? ? ? ? ? ? ?
2|0 ? ? ? ? ? ? ? ?
1|0 ? ? ? ? ? ? ? ?
  -----------------
  1 2 3 4 5 6 7 8 9

Z順で該当ノードから連結ノードに更新すれば、
解を求めることができると分かります。

nullable<long>型を使用したらTLEしたので
long型を使用してます。