ABC271-E Subsequence Path

問題へのリンク

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

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

    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]);
        long N = wkArr[0];
        long M = wkArr[1];

        var EdgeInfoList = new List<EdgeInfoDef>();
        foreach (string EachStr in InputList.Skip(1).Take((int)M)) {
            SplitAct(EachStr);
            EdgeInfoDef WillAdd;
            WillAdd.FromNode = wkArr[0];
            WillAdd.ToNode = wkArr[1];
            WillAdd.Cost = wkArr[2];
            EdgeInfoList.Add(WillAdd);
        }

        int[] EArr = InputList[InputList.Count - 1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        // 最短距離[ノード]なDP表
        var DPDict = new Dictionary<long, long>();
        DPDict[1] = 0;

        foreach (int EachE in EArr) {
            EdgeInfoDef CurrEdge = EdgeInfoList[EachE - 1];
            long FromNode = CurrEdge.FromNode;
            long ToNode = CurrEdge.ToNode;
            long Cost = CurrEdge.Cost;

            if (DPDict.ContainsKey(FromNode) == false) {
                continue;
            }

            long NewCost = DPDict[FromNode] + Cost;
            if (DPDict.ContainsKey(ToNode)) {
                if (DPDict[ToNode] <= NewCost) {
                    continue;
                }
            }
            DPDict[ToNode] = NewCost;
        }

        if (DPDict.ContainsKey(N)) {
            Console.WriteLine(DPDict[N]);
        }
        else {
            Console.WriteLine(-1);
        }
    }
}

解説

最短距離[ノード]を、辺の順番で更新するDPで解いてます。