第2回 CodeIQプロコン 3問目 復讐

■■■問題■■■

いくつかの狙撃目標地点について、各地点間の移動コストが与えられます。
たとえば次のような4地点について、1→3→2→4または4→2→3→1と移動すると移動コストは7となり、
他のどの移動方法よりも低コストになります。



このような、すべての地点を移動する、移動コストの最小値を求めてください。
最初の地点は任意です。最初の地点への移動コストは考えないものとします。

■■■入力■■■

標準入力から、1行目に整数値N (4 <= N <= 10)が与えられます。
2行目以降に、N個の整数値が半角スペースによって区切られたN行のデータ、つまりN*N個の整数値が与えられます。
これはNつの点同士の、移動にかかる時間を行列の形式で表したものです。
A→BとB→Aは同じ移動コストですので、左上から右下への対角線(0の部分)に対して必ず対称になっています。

■■■出力■■■

標準出力に、最小の移動コスト(整数値のみ)を出力してください。

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

    struct JyoutaiDef
    {
        internal int CurrPos;
        internal int SumCost;
        internal bool[] IsVisitedArr;
        //internal string Path;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        //隣接行列で枝を表現
        int[,] RinsetuGyouretu = new int[N, N];
        int UB = N - 1;
        for (int I = 0; I <= UB; I++) {
            int[] wkArr = InputList[I + 1].Split(' ').Select(X => int.Parse(X)).ToArray();
            for (int J = 0; J <= UB; J++) {
                RinsetuGyouretu[J, I] = wkArr[J];
            }
        }

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int I = 0; I <= UB; I++) {
            WillPush.CurrPos = I;
            WillPush.SumCost = 0;
            WillPush.IsVisitedArr = new bool[UB + 1];
            WillPush.IsVisitedArr[I] = true;
            //WillPush.Path = I.ToString();
            stk.Push(WillPush);
        }

        int AnswerCost = int.MaxValue;
        //string AnswerPath = "";
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Array.TrueForAll(Popped.IsVisitedArr, X => X)) {
                if (AnswerCost > Popped.SumCost) {
                    AnswerCost = Popped.SumCost;
                    //AnswerPath = Popped.Path;
                }
                continue;
            }

            for (int I = 0; I <= UB; I++) {
                if (Popped.IsVisitedArr[I])
                    continue;

                WillPush.CurrPos = I;
                WillPush.SumCost = Popped.SumCost + RinsetuGyouretu[Popped.CurrPos, I];

                //下限値枝切り
                if (WillPush.SumCost >= AnswerCost) {
                    continue;
                }
                WillPush.IsVisitedArr = (bool[])Popped.IsVisitedArr.Clone();
                WillPush.IsVisitedArr[I] = true;
                //WillPush.Path = Popped.Path + "," + I.ToString();

                stk.Push(WillPush);
            }
        }
        Console.WriteLine(AnswerCost);
    }
}

解説

深さ優先探索を使ってます。