ABC211-D Number of Shortest paths

問題へのリンク

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

    const long Hou = 1000000007;

    static int mN;

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeArrDict = new Dictionary<int, List<int>>();

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];

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

            if (mToNodeArrDict.ContainsKey(FromNode) == false) {
                mToNodeArrDict[FromNode] = new List<int>();
            }
            if (mToNodeArrDict.ContainsKey(ToNode) == false) {
                mToNodeArrDict[ToNode] = new List<int>();
            }
            mToNodeArrDict[FromNode].Add(ToNode);
            mToNodeArrDict[ToNode].Add(FromNode);
        }
        ExecBFS();
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal int Level;
        internal long PatternCnt;
    }

    // BFSを行う
    static void ExecBFS()
    {
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = 1;
        WillEnqueue.Level = 1;
        WillEnqueue.PatternCnt = 1;
        var Que = new Queue<JyoutaiDef>();
        Que.Enqueue(WillEnqueue);

        // 最短距離[ノード]なDict
        var MinCntDict = new Dictionary<int, long>();
        MinCntDict[1] = 1;

        // そのノードまでの最短距離が何通りあるか
        var OtherPathCntDict = new Dictionary<int, long>();

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

            if (OtherPathCntDict.ContainsKey(Dequeued.CurrNode)) {
                Dequeued.PatternCnt += OtherPathCntDict[Dequeued.CurrNode];
                Dequeued.PatternCnt %= Hou;
            }

            // クリア判定
            if (Dequeued.CurrNode == mN) {
                Answer += Dequeued.PatternCnt;
                Answer %= Hou;
                continue;
            }

            if (mToNodeArrDict.ContainsKey(Dequeued.CurrNode) == false) {
                continue;
            }
            foreach (int EachToNode in mToNodeArrDict[Dequeued.CurrNode]) {
                WillEnqueue.CurrNode = EachToNode;
                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.PatternCnt = Dequeued.PatternCnt;

                if (MinCntDict.ContainsKey(EachToNode)) {
                    // 遠回りの経路の場合
                    if (MinCntDict[EachToNode] < WillEnqueue.Level) {
                        continue;
                    }
                    // 最短経路の場合は、場合の数の和の法則
                    if (OtherPathCntDict.ContainsKey(EachToNode) == false) {
                        OtherPathCntDict[EachToNode] = 0;
                    }
                    OtherPathCntDict[EachToNode] += Dequeued.PatternCnt;
                    OtherPathCntDict[EachToNode] %= Hou;
                    continue;
                }
                MinCntDict[EachToNode] = WillEnqueue.Level;
                Que.Enqueue(WillEnqueue);
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

幅優先探索の動作をイメージしつつ、
現在ノードまでの最短経路が複数あったら、
それが何通りあるかを、状態に持つようにしてます。

類題

ABC021-C 正直者の高橋くん