結果

問題 No.1065 電柱 / Pole (Easy)
コンテスト
ユーザー Yusei Kato
提出日時 2020-06-26 11:14:08
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 5,620 bytes
コンパイル時間 2,514 ms
コンパイル使用メモリ 109,952 KB
実行使用メモリ 125,056 KB
最終ジャッジ日時 2024-07-03 22:12:38
合計ジャッジ時間 17,127 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 RE * 14 TLE * 2 -- * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections;
using System.Linq;

namespace Problem1065
{
    public class PriorityQueue<T> : IEnumerable<T>
    {
        private readonly List<T> _data;
        private readonly IComparer<T> _comparer;
        private readonly bool _isAscending;
        private  int Count { get; set; }

        public int GetCount()
        {
            return Count;
        }

        public PriorityQueue(IComparer<T> comparer, bool isAscending = true)
        {
            _data = new List<T>();
            _comparer = comparer;
            _isAscending = isAscending;
        }

        public PriorityQueue() : this (Comparer<T>.Default)
        {
            _data = new List<T>();
            _isAscending = true;
        }

        public void Enqueue(T item)
        {
            _data.Add(item);
            Count++;
            var childIndex = _data.Count - 1;
            while (childIndex > 0)
            {
                var parentIndex = (childIndex - 1) / 2;
                if (Compare(_data[childIndex], _data[parentIndex]) <= 0)
                {
                    break;
                }
                Swap(childIndex, parentIndex);
                childIndex = parentIndex;
            }
        }

        public T Dequeue()
        {
            var res = _data[0];
            _data[0] = _data[^1];
            _data.RemoveAt(_data.Count - 1);
            Count--;
            var parentIndex = 0;
            while ((parentIndex + 1) * 2 <= _data.Count)
            {
                var childIndex1 = (parentIndex + 1) * 2 - 1;
                if (childIndex1 + 1 == _data.Count)
                {
                    if (Compare(_data[childIndex1], _data[parentIndex]) >= 0)
                    {
                        break;
                    }
                    Swap(childIndex1, parentIndex);
                    parentIndex = childIndex1;
                }
                else
                {
                    var childIndex2 = childIndex1 + 1;
                    int childIndex;
                    childIndex = Compare(_data[childIndex1], _data[childIndex2]) >= 0 ? childIndex2 : childIndex1;
                    if (Compare(_data[childIndex], _data[parentIndex]) >= 0)
                    {
                        break;
                    }
                    Swap(childIndex, parentIndex);
                    parentIndex = childIndex;

                }
            }

            return res;
        }

        public T Peek() => _data[0];

        public IEnumerator<T> GetEnumerator() => _data.GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

        private int Compare(T a, T b)
        {
            return _isAscending ? _comparer.Compare(a, b) : _comparer.Compare(b, a);
        }

        private void Swap(int index1, int index2)
        {
            T temp;
            temp = _data[index1];
            _data[index1] = _data[index2];
            _data[index2] = temp;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var buff = GetLongArray();
            long N = buff[0];
            long M = buff[1];
            buff = GetLongArray();
            long start = buff[0];
            long goal = buff[1];

            var position = new long[N][];
            for(int i = 0; i < N; i++)
            {
                position[i] = GetLongArray();
            }
            var wire = new long[M][];
            for (int i = 0; i < M; i++)
            {
                wire[i] = GetLongArray();
            }
            var edge = new double[N, N];

            for(int i = 0; i < M; i++)
            {
                SearchIni(wire[i], edge, position);
            }
            Console.WriteLine(BFS(edge, goal - 1, start - 1));

        }
        public static void SearchIni(long[] raw, double[,] edge, long[][] position)
        {
            double distance = Math.Pow(Math.Pow(position[raw[0] - 1][0] - position[raw[1] - 1][0], 2) + Math.Pow(position[raw[0] - 1][1] - position[raw[1] - 1][1], 2), 0.5);
            if (distance == 0)
            {
                edge[raw[0] - 1, raw[1] - 1] = -1;
                edge[raw[1] - 1, raw[0] - 1] = -1;

            }
            else
            {
                edge[raw[0] - 1, raw[1] - 1] = distance;
                edge[raw[1] - 1, raw[0] - 1] = distance;
            }
        }

        public static double BFS(double[,] edge, long goal, long start)
        {
            var queue = new PriorityQueue<long>();
            queue.Enqueue(start);
            var distance = new double[edge.GetLength(0)];
            for (int i = 0; i < distance.Length; i++)
            {
                distance[i] = double.MaxValue;
            }

            distance[start] = 0;
            var searched = new HashSet<long>();

            while(queue.GetCount() != 0)
            {
                var current = queue.Dequeue();
                searched.Add(current);

                for(int i = 0; i < edge.GetLength(0); i++)
                {
                    if(edge[current, i] != 0 && !searched.Contains(i))
                    {
                        queue.Enqueue(i);
                        double temp = distance[current] + edge[current, i];
                        distance[i] = distance[i] > temp ? temp : distance[i];
                    }
                }
            }

            return distance[goal];
        }
        public static long[] GetLongArray() => Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
}
0