ABC369-E Sightseeing Tour

問題へのリンク

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 5");
            WillReturn.Add("1 2 10");
            WillReturn.Add("1 3 20");
            WillReturn.Add("1 3 30");
            WillReturn.Add("2 3 15");
            WillReturn.Add("2 3 25");
            WillReturn.Add("2");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3 5");
            //25
            //70
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 6");
            WillReturn.Add("1 5 1");
            WillReturn.Add("2 5 1");
            WillReturn.Add("2 4 1");
            WillReturn.Add("3 4 1");
            WillReturn.Add("3 6 1");
            WillReturn.Add("1 6 1");
            WillReturn.Add("2");
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4 5");
            WillReturn.Add("1");
            WillReturn.Add("5");
            //5
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 5");
            WillReturn.Add("1 2 1000000000");
            WillReturn.Add("2 3 1000000000");
            WillReturn.Add("3 4 1000000000");
            WillReturn.Add("4 5 1000000000");
            WillReturn.Add("1 5 1000000000");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("3");
            //4000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mNodeCnt;
    static long mEdgeCnt;

    struct EdgeInfoDef
    {
        internal long FromNode;
        internal long ToNode;
        internal long Cost;
    }
    static List<EdgeInfoDef> mEdgeInfoList = new List<EdgeInfoDef>();

    static long[,] mKyoriArr;

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

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

        SplitAct(InputList[0]);
        mNodeCnt = wkArr[0];
        mEdgeCnt = wkArr[1];

        foreach (string EachStr in InputList.Skip(1).Take((int)mEdgeCnt)) {
            SplitAct(EachStr);
            EdgeInfoDef WillAdd;
            WillAdd.FromNode = wkArr[0];
            WillAdd.ToNode = wkArr[1];
            WillAdd.Cost = wkArr[2];
            mEdgeInfoList.Add(WillAdd);
        }

        // ワーシャルフロイド法
        mKyoriArr = new long[mNodeCnt + 1, mNodeCnt + 1];

        const long INFTY = long.MaxValue;

        // 初期化処理
        for (int I = 0; I <= mNodeCnt; I++) {
            for (int J = 0; J <= mNodeCnt; J++) {
                mKyoriArr[I, J] = (I == J) ? 0 : INFTY;
            }
        }

        foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoList) {
            long FromNode = EachEdgeInfo.FromNode;
            long ToNode = EachEdgeInfo.ToNode;
            long Cost = EachEdgeInfo.Cost;
            mKyoriArr[FromNode, ToNode] = Math.Min(mKyoriArr[FromNode, ToNode], Cost);
            mKyoriArr[ToNode, FromNode] = Math.Min(mKyoriArr[ToNode, FromNode], Cost);
        }

        for (long K = 0; K <= mNodeCnt; K++) {
            for (long I = 0; I <= mNodeCnt; I++) {
                if (mKyoriArr[I, K] == INFTY) continue;
                for (long J = 0; J <= mNodeCnt; J++) {
                    if (mKyoriArr[K, J] == INFTY) continue;
                    long CurrKouho = mKyoriArr[I, K] + mKyoriArr[K, J];
                    if (mKyoriArr[I, J] > CurrKouho) {
                        mKyoriArr[I, J] = CurrKouho;
                    }
                }
            }
        }

        // クエリに回答
        for (int I = (int)mEdgeCnt + 3; I <= InputList.Count - 1; I += 2) {
            SplitAct(InputList[I]);
            long[] UseEdgeIndArr = wkArr;
            for (long J = 0; J <= UseEdgeIndArr.GetUpperBound(0); J++) {
                // 0オリジンに変更
                UseEdgeIndArr[J]--;
            }

            long Result = Solve(UseEdgeIndArr);
            Console.WriteLine(Result);
        }
    }

    // クエリに回答
    static long Solve(long[] pUseEdgeIndArr)
    {
        // 橋のIndの順列
        List<long[]> PermutationResult =
            RubyPatternClass<long>.Permutation(pUseEdgeIndArr, pUseEdgeIndArr.Length).ToList();

        // 橋の方向の順列
        var VectList = new List<long>() { 1, -1 };
        List<long[]> RepeatedPermutationResult =
            RubyPatternClass<long>.RepeatedPermutation(VectList, pUseEdgeIndArr.Length).ToList();

        var AnswerList = new List<long>();

        foreach (long[] EachArr1 in PermutationResult) {
            foreach (long[] EachArr2 in RepeatedPermutationResult) {
                long CostSum = SolveHelper(EachArr1, EachArr2);
                AnswerList.Add(CostSum);
            }
        }
        return AnswerList.Min();
    }

    static long SolveHelper(long[] pEdgeIndArr, long[] pVectArr)
    {
        long CostSum = 0;
        long CurrNode = 1;

        for (int I = 0; I <= pEdgeIndArr.GetUpperBound(0); I++) {
            EdgeInfoDef CurrEdge;

            if (pVectArr[I] == 1) {
                // 逆辺でない場合
                CurrEdge = mEdgeInfoList[(int)pEdgeIndArr[I]];
            }
            else {
                // 逆辺の場合
                CurrEdge.FromNode = mEdgeInfoList[(int)pEdgeIndArr[I]].ToNode;
                CurrEdge.ToNode = mEdgeInfoList[(int)pEdgeIndArr[I]].FromNode;
                CurrEdge.Cost = mEdgeInfoList[(int)pEdgeIndArr[I]].Cost;
            }

            CostSum += CurrEdge.Cost;
            CostSum += mKyoriArr[CurrNode, CurrEdge.FromNode];
            CurrNode = CurrEdge.ToNode;

            if (I == pEdgeIndArr.GetUpperBound(0)) {
                CostSum += mKyoriArr[CurrEdge.ToNode, mNodeCnt];
            }
        }
        return CostSum;
    }
}

#region RubyPatternClass
// Rubyの場合の数
internal static class RubyPatternClass<Type>
{
    // 順列を返す
    private struct JyoutaiDef_Permutation
    {
        internal List<int> SelectedIndList;
    }
    internal static IEnumerable<Type[]> Permutation(IEnumerable<Type> pEnum, int pR)
    {
        if (pR == 0) yield break;
        Type[] pArr = pEnum.ToArray();
        if (pArr.Length < pR) yield break;

        var Stk = new Stack<JyoutaiDef_Permutation>();
        JyoutaiDef_Permutation WillPush;
        for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
            WillPush.SelectedIndList = new List<int>() { I };
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            JyoutaiDef_Permutation Popped = Stk.Pop();

            // クリア判定
            if (Popped.SelectedIndList.Count == pR) {
                var WillReturn = new List<Type>();
                Popped.SelectedIndList.ForEach(X => WillReturn.Add(pArr[X]));
                yield return WillReturn.ToArray();
                continue;
            }

            for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
                if (Popped.SelectedIndList.Contains(I)) continue;
                WillPush.SelectedIndList = new List<int>(Popped.SelectedIndList) { I };
                Stk.Push(WillPush);
            }
        }
    }

    // 重複順列を返す
    private struct JyoutaiDef_RepeatedPermutation
    {
        internal List<int> SelectedIndList;
    }
    internal static IEnumerable<Type[]> RepeatedPermutation(IEnumerable<Type> pEnum, int pR)
    {
        if (pR == 0) yield break;
        Type[] pArr = pEnum.ToArray();

        var Stk = new Stack<JyoutaiDef_RepeatedPermutation>();
        JyoutaiDef_RepeatedPermutation WillPush;
        for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
            WillPush.SelectedIndList = new List<int>() { I };
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            JyoutaiDef_RepeatedPermutation Popped = Stk.Pop();

            // クリア判定
            if (Popped.SelectedIndList.Count == pR) {
                var WillReturn = new List<Type>();
                Popped.SelectedIndList.ForEach(X => WillReturn.Add(pArr[X]));
                yield return WillReturn.ToArray();
                continue;
            }

            for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
                WillPush.SelectedIndList = new List<int>(Popped.SelectedIndList) { I };
                Stk.Push(WillPush);
            }
        }
    }
}
#endregion

解説

ワーシャルフロイド法で全点対間の最短距離を求めてます。

それから
{橋を渡る順番の順列}と{橋の方向の全組合せ}
の組合せを全て調べてます。

例えば、橋が5本なら
{橋を渡る順番の順列}は5*4*3*2
{橋の方向の全組合せ}は2の5乗
となり、その組合せは、積の法則で 5*4*3*2*(2の5乗)です。