TopCoder SRM 144 DIV 2 Hard 練習

問題

木構造の根から出発して、全ての葉を回る最短経路を求める問題。

解

問題が読めればあとは実装するだけ。根から全ての葉にたどり着くことができるので、根から葉までの距離が一番大きい葉を一番後回しにすればおｋ。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class PowerOutage {
    public int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) {
        int N = 50;
        int[,] graph = new int[N, N];

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                graph[i, j] = -1;

        int ret = 0;
        for (int i = 0; i < fromJunction.Length; ++i)
        {
            graph[fromJunction[i], toJunction[i]] = ductLength[i];
            graph[toJunction[i], fromJunction[i]] = ductLength[i];
            ret += ductLength[i] * 2;   // 往復
        }

        while (true)
        {
            bool change = false;
            for(int i = 0; i < N; ++i)
                for(int j = i+1; j < N; ++j)
                    for (int k = 0; k < N; ++k)
                    {
                        if (graph[i, k] < 0 || graph[k, j] < 0)
                            continue;
                        if (graph[i, j] < 0 || graph[i, j] > graph[i, k] + graph[k, j])
                        {
                            graph[j, i] = graph[i, j] = graph[i, k] + graph[k, j];    // 道をつなげる
                            change = true;
                        }
                    }
            if (!change)
                break;
        }

        int cut = 0;
        for (int i = 0; i < N; ++i)
            cut = Math.Max(cut, graph[0, i]);
        return ret - cut;
    }
}