ABC180-E Traveling Salesman among Aerial Cities

問題へのリンク

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("2");
            WillReturn.Add("0 0 0");
            WillReturn.Add("1 2 3");
            //9
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 0 0");
            WillReturn.Add("1 1 1");
            WillReturn.Add("-1 -1 -1");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("17");
            WillReturn.Add("14142 13562 373095");
            WillReturn.Add("-17320 508075 68877");
            WillReturn.Add("223606 -79774 9979");
            WillReturn.Add("-24494 -89742 783178");
            WillReturn.Add("26457 513110 -64591");
            WillReturn.Add("-282842 7124 -74619");
            WillReturn.Add("31622 -77660 -168379");
            WillReturn.Add("-33166 -24790 -3554");
            WillReturn.Add("346410 16151 37755");
            WillReturn.Add("-36055 51275 463989");
            WillReturn.Add("37416 -573867 73941");
            WillReturn.Add("-3872 -983346 207417");
            WillReturn.Add("412310 56256 -17661");
            WillReturn.Add("-42426 40687 -119285");
            WillReturn.Add("43588 -989435 -40674");
            WillReturn.Add("-447213 -59549 -99579");
            WillReturn.Add("45825 7569 45584");
            //6519344
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int UB;

    struct XYZInfoDef
    {
        internal int X;
        internal int Y;
        internal int Z;
    }
    static XYZInfoDef[] mXYZInfoArr;

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        mN = int.Parse(InputList[0]);
        UB = mN - 1;

        var XYZInfoList = new List<XYZInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYZInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.Z = wkArr[2];
            XYZInfoList.Add(WillAdd);
        }
        mXYZInfoArr = XYZInfoList.ToArray();
        Solve();
    }

    static void Solve()
    {
        int AllBitOn = (1 << mN) - 1;

        // 最小コスト[現在ノード , 訪問済ノードセット] なDP表
        int?[,] PrevDP = new int?[mN + 1, AllBitOn + 1];
        PrevDP[0, 0] = 0;

        for (int I = 1; I <= mN; I++) {
            int?[,] CurrDP = new int?[mN + 1, AllBitOn + 1];
            for (int J = 0; J <= mXYZInfoArr.GetUpperBound(0); J++) {
                // ノード0に訪問できるのは最後のみ
                if (J == 0 && I < mN) continue;

                // ビットシフトする必要あり
                int JBit = (1 << J);

                for (int K = 0; K <= mN - 1; K++) {
                    for (int L = 0; L <= AllBitOn; L++) {
                        if (PrevDP[K, L].HasValue == false) continue;

                        // 再訪は不可
                        if ((L & JBit) > 0) continue;

                        int NewK = J;
                        int NewL = L | JBit;

                        int NewVal = PrevDP[K, L].Value;
                        NewVal += Math.Abs(mXYZInfoArr[J].X - mXYZInfoArr[K].X);
                        NewVal += Math.Abs(mXYZInfoArr[J].Y - mXYZInfoArr[K].Y);
                        NewVal += Math.Max(0, mXYZInfoArr[J].Z - mXYZInfoArr[K].Z);
                        if (CurrDP[NewK, NewL].HasValue) {
                            if (CurrDP[NewK, NewL].Value <= NewVal) {
                                continue;
                            }
                        }
                        CurrDP[NewK, NewL] = NewVal;
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[0, AllBitOn]);
    }
}

解説

任意の2点間の移動は、直接移動するのが最小コストであることをふまえて、
TSP問題として、BitDPで解いてます。