結果

問題 No.386 貪欲な領主
コンテスト
ユーザー mban
提出日時 2016-11-04 05:14:24
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 1,872 bytes
コンパイル時間 2,750 ms
コンパイル使用メモリ 116,992 KB
実行使用メモリ 91,620 KB
最終ジャッジ日時 2024-11-25 02:29:49
合計ジャッジ時間 21,747 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Magatro
{
    static int N, M;
    static List<int>[] Root;
    static int[] U;
    static void Main()
    {
        Read();
        int m = int.Parse(Console.ReadLine());
        long cnt = 0;
        for(int i = 0; i < m; i++)
        {
            int[] abc = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            cnt += calc(abc[0], abc[1]) * abc[2];
        }
        Console.WriteLine(cnt);
    }
    static int calc(int s, int g)
    {
        int[] miti = new int[N];
        bool[] ed = new bool[N];
        miti[s] = U[s];
        ed[s] = true;
        Queue<int> q = new Queue<int>();
        q.Enqueue(s);
        while (q.Count > 0)
        {
            int i = q.Dequeue();
            for (int j = 0; j < Root[i].Count; j++)
            {
                int w = Root[i][j];

                if (!ed[w])
                {
                    q.Enqueue(w);
                    ed[w] = true;

                    miti[w] = miti[i] + U[w];
                    if (w == g)
                    {
                        return miti[g];
                    }
                }
            }
        }
        return -1;
    }
    static void Read()
    {
        N = int.Parse(Console.ReadLine());
        Root = new List<int>[N];
     
        for (int i = 0; i < N; i++)
        {
            Root[i] = new List<int>();
        }
        for (int i = 0; i < N - 1; i++)
        {
            string[] s = Console.ReadLine().Split(' ');
            int a = int.Parse(s[0]);
            int b = int.Parse(s[1]);
            Root[a].Add(b);
            Root[b].Add(a);
        }
        U = new int[N];
        for(int i = 0; i < N; i++)
        {
            U[i] = int.Parse(Console.ReadLine());
        }
    }
}
0