第17回PAST L 割引券

問題へのリンク

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("4");
            WillReturn.Add("4 8 5");
            WillReturn.Add("6 8");
            WillReturn.Add("3");
            WillReturn.Add("1 6 1");
            WillReturn.Add("5 2");
            WillReturn.Add("1");
            //1 4 1
            //5 2
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("2255 36 196 3623 6579");
            WillReturn.Add("681 183 473 8830");
            WillReturn.Add("7549 743 8216");
            WillReturn.Add("1078 9");
            WillReturn.Add("224");
            WillReturn.Add("105 3 1 810 15");
            WillReturn.Add("7 125 11 3");
            WillReturn.Add("50 6 1781");
            WillReturn.Add("537 4");
            WillReturn.Add("85");
            //43 3 1 42 10
            //7 12 11 3
            //37 6 46
            //94 4
            //85
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        long N = long.Parse(InputList[0]);
        long UB = 2 * N - 1;

        long[,] KyoriArr = new long[UB + 1, UB + 1];

        const long INFTY = long.MaxValue;

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

        // 割引を使わない辺のコストを設定
        for (long I = 1; I <= N - 1; I++) {
            SplitAct(InputList[(int)I]);

            long FromNode1 = I - 1;
            for (long J = 0; J <= wkArr.GetUpperBound(0); J++) {
                long ToNode = I + J;
                long Cost = wkArr[J];
                KyoriArr[FromNode1, ToNode] = Cost;
                KyoriArr[ToNode, FromNode1] = Cost;

                KyoriArr[FromNode1 + N, ToNode + N] = Cost;
                KyoriArr[ToNode + N, FromNode1 + N] = Cost;
            }
        }

        // 割引を使う辺のコストを設定
        long FromNode2 = 0;
        foreach (string EachStr in InputList.Skip((int)N)) {
            SplitAct(EachStr);
            for (long J = 0; J <= wkArr.GetUpperBound(0); J++) {
                long ToNode = FromNode2 + J + 1;
                long Cost = wkArr[J];
                KyoriArr[FromNode2, ToNode + N] = Cost;
                KyoriArr[ToNode, FromNode2 + N] = Cost;
            }

            FromNode2++;
        }

        // ワーシャルフロイド法
        for (int K = 0; K <= UB; K++) {
            for (int I = 0; I <= UB; I++) {
                if (KyoriArr[I, K] == INFTY) continue;
                for (int J = 0; J <= UB; J++) {
                    if (KyoriArr[K, J] == INFTY) continue;
                    long CurrKouho = KyoriArr[I, K] + KyoriArr[K, J];
                    if (KyoriArr[I, J] > CurrKouho) {
                        KyoriArr[I, J] = CurrKouho;
                    }
                }
            }
        }

        for (long I = 0; I <= N - 2; I++) {
            var AnswerList = new List<long>();
            for (long J = I + 1; J <= N - 1; J++) {
                long FromNode = I;
                long ToNode = J + N;

                long Cost = KyoriArr[FromNode, ToNode];
                AnswerList.Add(Cost);
            }
            Console.WriteLine(LongEnumJoin(" ", AnswerList));
        }
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

割引券使用前の世界と
割引券使用後の世界で
頂点を倍加して、ワーシャルフロイド法を使ってます。