ABC137-E Coins Respawn

問題へのリンク

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

    struct EdgeInfoDef
    {
        internal long ToNode;
        internal long Cost;
    }

    // 隣接リスト (正方向)
    static Dictionary<long, List<EdgeInfoDef>> mSeiEdgeListDict = new Dictionary<long, List<EdgeInfoDef>>();

    // 隣接リスト (逆方向)
    static Dictionary<long, List<EdgeInfoDef>> mRevEdgeListDict = new Dictionary<long, List<EdgeInfoDef>>();

    static long mN;
    static long mP;

    // Nから逆辺を使ったDFSで、Nに遷移できるノード
    static HashSet<long> mConnectGoalNodeSet;

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

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

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

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

            if (mSeiEdgeListDict.ContainsKey(FromNode) == false) {
                mSeiEdgeListDict[FromNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd1;
            WillAdd1.ToNode = ToNode;
            WillAdd1.Cost = Cost;

            // 枝のコストからPを引いておく
            WillAdd1.Cost -= mP;

            mSeiEdgeListDict[FromNode].Add(WillAdd1);

            // 逆辺の隣接リストも用意する
            if (mRevEdgeListDict.ContainsKey(ToNode) == false) {
                mRevEdgeListDict[ToNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd2;
            WillAdd2.ToNode = FromNode;
            WillAdd2.Cost = Cost;
            mRevEdgeListDict[ToNode].Add(WillAdd2);
        }

        // 前処理として、Nから逆辺を使ったDFSで、Nに遷移できるノードを列挙
        mConnectGoalNodeSet = DeriveConnectGoalNodeSet();

        Solve();
    }

    struct JyoutaiDef
    {
        internal long CurrNode;
    }

    // 前処理として、Nから逆辺を使ったDFSで、Nに遷移できるノードを列挙
    static HashSet<long> DeriveConnectGoalNodeSet()
    {
        var WillReturn = new HashSet<long>();

        JyoutaiDef WillPush;
        WillPush.CurrNode = mN;

        var Stk = new Stack<JyoutaiDef>();
        Stk.Push(WillPush);

        WillReturn.Add(mN);
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (mRevEdgeListDict.ContainsKey(Popped.CurrNode) == false) {
                continue;
            }

            foreach (EdgeInfoDef EachEdgeInfo in mRevEdgeListDict[Popped.CurrNode]) {
                if (WillReturn.Add(EachEdgeInfo.ToNode)) {
                    WillPush.CurrNode = EachEdgeInfo.ToNode;
                    Stk.Push(WillPush);
                }
            }
        }
        return WillReturn;
    }

    static void Solve()
    {
        // 各ノードまでのスコアのDict
        var SumScoreDict = new Dictionary<long, long>();
        SumScoreDict[1] = 0;

        // ベルマンフォード法で解く
        bool WillBreak = false;
        for (int I = 1; I <= mN; I++) {
            WillBreak = true;

            foreach (int EachKey in SumScoreDict.Keys.ToArray()) {
                if (mSeiEdgeListDict.ContainsKey(EachKey) == false)
                    continue;

                // そのノードから訪問可能なノードで
                // 最大コストを更新可能なら更新
                foreach (EdgeInfoDef EachNodeInfo in mSeiEdgeListDict[EachKey]) {
                    if (mConnectGoalNodeSet.Contains(EachNodeInfo.ToNode) == false) {
                        continue;
                    }

                    long wkSumScore = SumScoreDict[EachKey] + EachNodeInfo.Cost;
                    if (SumScoreDict.ContainsKey(EachNodeInfo.ToNode)) {
                        if (SumScoreDict[EachNodeInfo.ToNode] >= wkSumScore) {
                            continue;
                        }
                    }
                    SumScoreDict[EachNodeInfo.ToNode] = wkSumScore;
                    WillBreak = false;
                }
            }
            if (WillBreak) break;
        }

        if (WillBreak) {
            Console.WriteLine(Math.Max(0, SumScoreDict[mN]));
        }
        else {
            Console.WriteLine("-1");
        }
    }
}

解説

前処理として、ゴールから逆辺を使ってDFSを行い、
ゴールに到達可能なノードを列挙します。

次に、ゴールに到達可能なノードのみで
ベルマンフォード法で最長経路を求めます。

ベルマンフォード法での最長経路の更新が
N回で収束したかを調べれば、
正の閉路の有無が判定できます。

類題

ABC061-D Score Attack