ABC061-D Score Attack

■■■問題■■■

N頂点M辺の重み付き有向グラフがあります。
i(1 <= i <= M) 番目の辺は 頂点aiから 頂点biを重みciで結びます。
このグラフと駒を利用して、次の1人ゲームを行います。

最初、駒を頂点1に置いて、プレイヤーのスコアを0とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。

●頂点aiに駒があるとき、i番目の辺を利用して頂点biに移動する。
  移動後にプレイヤーのスコアがci加算される。

頂点Nに駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点1から頂点Nに移動できることは保障されています。

プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、
ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合はinfと出力してください。

■■■入力■■■

N M
a1 b1 c1
a2 b2 c2
・
・
・
aM bM cM

●2 <= N <= 1000
●1 <= M <= min(N(N-1),2000)
●1 <= ai,bi <= N(1 <= i <= M)
●ai != bi(1 <= i <= M)
●ai != aj または bi != bj(1 <= i<j <= M)
●-10億 <= ci <= 10億(1 <= i <= M)
●ciは整数である
●与えられるグラフには、頂点1から頂点Nへの経路が存在する

■■■出力■■■

もし、ゲーム終了時のスコアをいくらでも大きくできる場合はinf、
そうでない場合はゲーム終了時のスコアの最大値を出力せよ。

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");
            WillReturn.Add("1 2 4");
            WillReturn.Add("2 3 3");
            WillReturn.Add("1 3 5");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add("1 2 1");
            WillReturn.Add("2 1 1");
            //inf
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 5");
            WillReturn.Add("1 2 -1000000000");
            WillReturn.Add("2 3 -1000000000");
            WillReturn.Add("3 4 -1000000000");
            WillReturn.Add("4 5 -1000000000");
            WillReturn.Add("5 6 -1000000000");
            //-5000000000
        }
        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;

    // 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];

        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;

            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(SumScoreDict[mN]);
        }
        else {
            Console.WriteLine("inf");
        }
    }
}

解説

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

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

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

類題

ABC137-E Coins Respawn