GRL_1_B: Single Source Shortest Path (Negative Edges)

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q052 ベルマンフォード法 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5 0");
            WillReturn.Add("0 1 2");
            WillReturn.Add("0 2 3");
            WillReturn.Add("1 2 -5");
            WillReturn.Add("1 3 1");
            WillReturn.Add("2 3 2");
            //0
            //2
            //-3
            //-1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 6 0");
            WillReturn.Add("0 1 2");
            WillReturn.Add("0 2 3");
            WillReturn.Add("1 2 -5");
            WillReturn.Add("1 3 1");
            WillReturn.Add("2 3 2");
            WillReturn.Add("3 1 0");
            //NEGATIVE CYCLE
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 5 1");
            WillReturn.Add("0 1 2");
            WillReturn.Add("0 2 3");
            WillReturn.Add("1 2 -5");
            WillReturn.Add("1 3 1");
            WillReturn.Add("2 3 2");
            //INF
            //0
            //-5
            //-3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mV; // 頂点の数
    static int mR; // 開始頂点

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

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

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

        SplitAct(InputList[0]);
        mV = wkArr[0];
        mR = wkArr[2];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int FromNode = wkArr[0];
            if (mEdgeInfoListDict.ContainsKey(FromNode) == false) {
                mEdgeInfoListDict[FromNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd;
            WillAdd.ToNode = wkArr[1];
            WillAdd.Cost = wkArr[2];
            mEdgeInfoListDict[FromNode].Add(WillAdd);
        }

        // ベルマンフォード法
        BellmanFord();
    }

    // ベルマンフォード法
    static void BellmanFord()
    {
        //各ノードまでの距離のDict
        var SumCostDict = new Dictionary<int, int>();
        SumCostDict[mR] = 0;

        // 頂点数だけループ
        bool WillBreak = false;
        for (int I = 1; I <= mV; I++) {
            WillBreak = true;

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

                // そのノードから訪問可能なノードで
                // 最短距離を更新可能なら更新
                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[EachKey]) {
                    int wkSumCost = SumCostDict[EachKey] + EachEdgeInfo.Cost;
                    if (SumCostDict.ContainsKey(EachEdgeInfo.ToNode)) {
                        if (SumCostDict[EachEdgeInfo.ToNode] <= wkSumCost) {
                            continue;
                        }
                    }
                    SumCostDict[EachEdgeInfo.ToNode] = wkSumCost;
                    WillBreak = false;
                }
            }
            if (WillBreak) break;
        }
        if (WillBreak == false) {
            Console.WriteLine("NEGATIVE CYCLE");
        }
        else {
            for (int I = 0; I <= mV - 1; I++) {
                if (SumCostDict.ContainsKey(I)) {
                    Console.WriteLine(SumCostDict[I]);
                }
                else {
                    Console.WriteLine("INF");
                }
            }
        }
    }
}

解説

ベルマンフォード法で解いてます。
(頂点数-1)回のループで最短距離の更新が完了しなかったら、
負の閉路があると判定してます。

類題

ABC-061-D Score Attack