第3回PAST M 行商計画問題

問題へのリンク

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("3 2");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("2");
            WillReturn.Add("2");
            WillReturn.Add("1 3");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 5");
            WillReturn.Add("1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("1 4");
            WillReturn.Add("1 5");
            WillReturn.Add("2 3");
            WillReturn.Add("1");
            WillReturn.Add("3");
            WillReturn.Add("2 3 5");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    static int mS;
    static int mK;
    static int[] mTArr;

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

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

        SplitAct(InputList[0]);
        int M = wkArr[1];

        foreach (string EachStr in InputList.Skip(1).Take(M)) {
            SplitAct(EachStr);
            int U = wkArr[0];
            int V = wkArr[1];

            if (mEdgeInfoListDict.ContainsKey(U) == false) {
                mEdgeInfoListDict[U] = new List<int>();
            }
            mEdgeInfoListDict[U].Add(V);
            if (mEdgeInfoListDict.ContainsKey(V) == false) {
                mEdgeInfoListDict[V] = new List<int>();
            }
            mEdgeInfoListDict[V].Add(U);
        }

        mS = int.Parse(InputList[M + 1]);
        mK = int.Parse(InputList[M + 2]);
        mTArr = InputList[M + 3].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        var FromNodeList = new List<int>();
        FromNodeList.Add(mS);
        FromNodeList.AddRange(mTArr);

        // 各ノードまでの最短距離を求めておく
        var EdgeInfoListDict = new SortedDictionary<int, List<EdgeInfoDef>>();
        foreach (int EachFromNode in FromNodeList) {
            EdgeInfoListDict[EachFromNode] = ExecBFS(EachFromNode);
        }

        var KyoriDict = new Dictionary<long, int>();
        foreach (var EachPair in EdgeInfoListDict) {
            foreach (EdgeInfoDef EachEdgeInfo in EachPair.Value) {
                long Hash = GetPairHash(EachPair.Key, EachEdgeInfo.ToNode);
                KyoriDict[Hash] = EachEdgeInfo.Cost;
            }
        }

        int UB = mTArr.GetUpperBound(0);
        int CompleteKey = (1 << mK) - 1;

        // 最小コスト[現在位置,訪問済なmTArrの添字] なDP表
        int?[,] PrevDP = new int?[UB + 1, CompleteKey + 1];

        foreach (EdgeInfoDef EachEdgeInfo in EdgeInfoListDict[mS]) {
            int ToNode = EachEdgeInfo.ToNode;
            int Cost = EachEdgeInfo.Cost;
            int TArrInd = Array.IndexOf(mTArr, ToNode);

            PrevDP[TArrInd, 1 << TArrInd] = Cost;
        }

        for (int I = 1; I <= mK - 1; I++) {
            int?[,] CurrDP = new int?[UB + 1, CompleteKey + 1];

            for (int J = 0; J <= UB; J++) {
                for (int K = 0; K <= CompleteKey; K++) {
                    if (PrevDP[J, K].HasValue == false) continue;
                    for (int L = 0; L <= UB; L++) {
                        int CurrBit = 1 << L;
                        if ((K & CurrBit) > 0) continue;

                        int NewJ = L;
                        int NewK = K + CurrBit;

                        long Hash = GetPairHash(mTArr[J], mTArr[L]);
                        int NewVal = PrevDP[J, K].Value + KyoriDict[Hash];
                        if (CurrDP[NewJ, NewK].HasValue) {
                            if (CurrDP[NewJ, NewK].Value <= NewVal) {
                                continue;
                            }
                        }
                        CurrDP[NewJ, NewK] = NewVal;
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Cast<int?>().Min());
    }

    static long GetPairHash(int pFrom, int pTo)
    {
        return pFrom * 1000000 + pTo;
    }

    struct EdgeInfoDef
    {
        internal int ToNode;
        internal int Cost;
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal int Cost;
    }

    static List<EdgeInfoDef> ExecBFS(int pStaNode)
    {
        var WillReturn = new List<EdgeInfoDef>();

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = pStaNode;
        WillEnqueue.Cost = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(pStaNode);

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (Array.IndexOf(mTArr, Dequeued.CurrNode) >= 0) {
                EdgeInfoDef WillAdd;
                WillAdd.ToNode = Dequeued.CurrNode;
                WillAdd.Cost = Dequeued.Cost;
                WillReturn.Add(WillAdd);
            }

            if (mEdgeInfoListDict.ContainsKey(Dequeued.CurrNode)) {
                foreach (int EachToNode in mEdgeInfoListDict[Dequeued.CurrNode]) {
                    if (VisitedSet.Add(EachToNode)) {
                        WillEnqueue.CurrNode = EachToNode;
                        WillEnqueue.Cost = Dequeued.Cost + 1;
                        Que.Enqueue(WillEnqueue);
                    }
                }
            }
        }
        return WillReturn;
    }
}

解説

全ての辺のコストが1なので
最初に、幅優先探索で
訪問が必要なノード同士の最短距離を求めてます。

次に、巡回セールスマン問題の要領で
BitDPしてます。

類題

ABC190-E Magical Ornament