yukicoder No.1 道のショートカット

問題リンク

No.1 道のショートカット - yukicoder

問題概要

• 町まで個の町がある。
• 一方通行の道が本あり、 () 番目の道は町から町をつないでいる。(町から町へは行けない)
• で閉路はない。
• 番目の道を通るのに円が必要で単位時間かかる。
• 円以内で町から出発して町まで移動するルートのうち、最も時間が短くなる方法で移動するとしたときの時間を求める。
• そのようなルートがない場合は-1を出力。

制約

• 
• 
• 
• 
• 
• 
• 

解説

かかった時間の最小値 として計算する。(DP)
DAGででも正なのでかかった金額がCを超えないようにループを回せばいい。
計算量はたぶん

ソースコード(C#)

#147241
テンプレート、入力は省略

public class Magatro
{
    private int N, C, V;
    private int[] S, T, Y, M;

    int Infinity = int.MaxValue;

    //iの町からGraph[i].Tの町までYのコストで時間M
    private List<Road>[] Graph;

    //[現在の町の位置,かかるコスト]
    private int[,] Time;

    public void Solve()
    {
        InitGraph();
        InitTime();
        Calc();
        Write();
    }

    //S,T,Y,MをGraphに入れる
    private void InitGraph()
    {
        Graph = new List<Road>[N];

        for (int i = 0; i < N; i++)
        {
            Graph[i] = new List<Road>();
        }

        for (int i = 0; i < V; i++)
        {
            Graph[S[i]-1].Add(new Road(T[i] - 1, Y[i], M[i]));
        }
    }

    //Timeの値をInfinityにして初期化
    private void InitTime()
    {
        Time = new int[N, C + 1];

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j <= C; j++)
            {
                Time[i, j] = Infinity;
            }
        }
    }

    private void Calc()
    {
        Time[0, 0] = 0;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j <= C; j++)
            {
                if (Time[i, j] != Infinity)
                {
                    foreach (Road r in Graph[i])
                    {
                        //コストがC以下なら
                        if (j + r.Y <= C)
                        {
                            //Timeを更新
                            Time[r.T, j + r.Y] = Math.Min(Time[r.T, j + r.Y], Time[i, j] + r.M);
                        }
                    }
                }
            }
        }
    }

    private void Write()
    {
        int anser = int.MaxValue;
        bool flag = false;

        for(int i = 0; i <= C; i++)
        {
            if (Time[N - 1, i] != Infinity)
            {
                //flagを立ててanserを更新
                anser = Math.Min(anser, Time[N - 1, i]);
                flag = true;
            }
        }

        if (flag)
        {
            Console.WriteLine(anser);
        }
        else
        {
            //flagが立ってない。つまりNに行くルートがない
            Console.WriteLine(-1);
        }
    }
}

struct Road
{
    public int T, Y, M;

    public Road(int t,int y,int m)
    {
        T = t;
        Y = y;
        M = m;
    }
}

最後に

初めて解説をした。むずい
説明不足のところがあるかもしれない。(というより絶対にある)
これってDPでいいのかしら。
Calc( )のネストが深すぎるしTime[,]を更新するところももう少し上手く書く方法がある気がする。
というよりなんか読みにくい。
まだまだ実力が足りない。