AtCoderのABC    前のABCの問題へ

ABC485-E Colorful Route


問題へのリンク


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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct EdgeInfoDef
    {
        internal long ToNode;
        internal long Color;
    }
    static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long NodeCnt = wkArr[0];

        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long Color = wkArr[2];

            if (mEdgeInfoListDict.ContainsKey(FromNode) == false) {
                mEdgeInfoListDict[FromNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd;
            WillAdd.ToNode = ToNode;
            WillAdd.Color = Color;
            mEdgeInfoListDict[FromNode].Add(WillAdd);
        }

        var Que = new Queue<JyoutaiDef>();

        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = 1;
        WillEnqueue.SumCost = 0;
        WillEnqueue.PrevColor = 0;
        Que.Enqueue(WillEnqueue);

        // 訪問数[ノード]なDict
        var VisitedSet = new HashSet<long>();

        // 訪問数[ノード]なDict
        var VisitedCntDict = new Dictionary<long, long>();

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

            if (Dequeued.CurrNode == NodeCnt) {
                Console.WriteLine(Dequeued.SumCost);
                return;
            }

            // 遷移
            if (mEdgeInfoListDict.ContainsKey(Dequeued.CurrNode)) {
                foreach (EdgeInfoDef EachEdge in mEdgeInfoListDict[Dequeued.CurrNode]) {
                    if (EachEdge.Color == Dequeued.PrevColor) continue;

                    WillEnqueue.CurrNode = EachEdge.ToNode;
                    WillEnqueue.SumCost = Dequeued.SumCost + 1;
                    WillEnqueue.PrevColor = EachEdge.Color;

                    // 最訪防止
                    long CurrHash = GetHash(WillEnqueue.CurrNode, WillEnqueue.PrevColor);
                    if (VisitedSet.Add(CurrHash) == false) {
                        continue;
                    }

                    // 枝切り
                    if (VisitedCntDict.ContainsKey(WillEnqueue.CurrNode)) {
                        if (VisitedCntDict[WillEnqueue.CurrNode] == 2) {
                            continue;
                        }
                    }
                    else {
                        VisitedCntDict[WillEnqueue.CurrNode] = 0;
                    }
                    VisitedCntDict[WillEnqueue.CurrNode]++;

                    Que.Enqueue(WillEnqueue);
                }
            }
        }
        Console.WriteLine(-1);
    }

    struct JyoutaiDef
    {
        internal long CurrNode;
        internal long SumCost;
        internal long PrevColor;
    }

    static long GetHash(long pNode, long pColor)
    {
        return pNode * 1000000 + pColor;
    }
}


解説

頂点倍加で、{ノード、直前の色}をノードとし、
最訪防止のBFSすることを考えます。

BFSの計算量は、O(ノード数 + 枝数)であり、
{ノード、直前の色}で頂点倍加したら、
ノード数がNMあるので、ノード数の分だけでもTLEします。

そこで、ノードから色1,2,3,4,5の辺があるとして、枝切りを考えます。
1の色の辺から当該ノードに到達したら、色2,3,4,5の辺が使えます。
次の訪問で、1の色の辺以外から当該ノードに到達したら
色1の辺が使えます。

{ノード、直前の色}で最訪防止なBFSをしてることも考慮すると、
同じノードの3回目の訪問は、枝切りして良いと分かります。

これで、頂点倍加したグラフの、ノード数と枝数が激減するので
計算量を減らすことができ、TLEせずにACできます。