ABC286-E Souvenir

問題へのリンク

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("5");
            WillReturn.Add("30 50 70 20 60");
            WillReturn.Add("NYYNN");
            WillReturn.Add("NNYNN");
            WillReturn.Add("NNNYY");
            WillReturn.Add("YNNNN");
            WillReturn.Add("YNNNN");
            WillReturn.Add("3");
            WillReturn.Add("1 3");
            WillReturn.Add("3 1");
            WillReturn.Add("4 5");
            //1 100
            //2 160
            //3 180
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("100 100");
            WillReturn.Add("NN");
            WillReturn.Add("NN");
            WillReturn.Add("1");
            WillReturn.Add("1 2");
            //Impossible
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct CostDef
    {
        internal long EdgeCnt;
        internal long OmiyageSum;
    }

    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 = N - 1;

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        CostDef?[,] CostArr = new CostDef?[UB + 1, UB + 1];

        // 隣接行列を作る
        long FromNode = 0;
        foreach (string EachStr in InputList.Skip(2).Take((int)N)) {
            for (long I = 0; I <= EachStr.Length - 1; I++) {
                if (EachStr[(int)I] == 'N') continue;
                long ToNode = I;
                CostDef WillSet;
                WillSet.EdgeCnt = 1;
                WillSet.OmiyageSum = AArr[I];
                CostArr[FromNode, ToNode] = WillSet;
            }
            FromNode++;
        }

        // ワーシャルフロイド法
        for (long K = 0; K <= UB; K++) {
            for (long I = 0; I <= UB; I++) {
                if (CostArr[I, K].HasValue == false) continue;
                for (long J = 0; J <= UB; J++) {
                    if (CostArr[K, J].HasValue == false) continue;
                    CostDef NewCost;
                    NewCost.EdgeCnt = CostArr[I, K].Value.EdgeCnt + CostArr[K, J].Value.EdgeCnt;
                    NewCost.OmiyageSum = CostArr[I, K].Value.OmiyageSum + CostArr[K, J].Value.OmiyageSum;

                    bool CanSet = true;
                    if (CostArr[I, J].HasValue) {
                        if (CostArr[I, J].Value.EdgeCnt < NewCost.EdgeCnt) {
                            CanSet = false;
                        }
                        if (CostArr[I, J].Value.EdgeCnt == NewCost.EdgeCnt) {
                            if (CostArr[I, J].Value.OmiyageSum > NewCost.OmiyageSum) {
                                CanSet = false;
                            }
                        }
                    }
                    if (CanSet) {
                        CostArr[I, J] = NewCost;
                    }
                }
            }
        }

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(2 + (int)N + 1)) {
            SplitAct(EachStr);
            long StaNode = wkArr[0] - 1;
            long GoalNode = wkArr[1] - 1;

            if (CostArr[StaNode, GoalNode].HasValue) {
                long EdgeCnt = CostArr[StaNode, GoalNode].Value.EdgeCnt;
                long OmiyageSum = CostArr[StaNode, GoalNode].Value.OmiyageSum;
                OmiyageSum += AArr[StaNode];

                sb.AppendFormat("{0} {1}", EdgeCnt, OmiyageSum);
                sb.AppendLine();
            }
            else {
                sb.AppendLine("Impossible");
            }
        }
        Console.Write(sb.ToString());
    }
}

解説

ワーシャルフロイド法はDPなので、
全点対間の最小コストを
最小コスト[始点ノード , 終点ノード]
を更新するDPで求めてます。