結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー fairy_lettuce
提出日時 2020-05-29 22:07:22
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 9,582 bytes
コンパイル時間 5,042 ms
コンパイル使用メモリ 118,476 KB
実行使用メモリ 513,208 KB
最終ジャッジ日時 2024-11-06 04:58:08
合計ジャッジ時間 6,250 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other RE * 7 MLE * 1 -- * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace AtCoder.Contest.C
{
    static class Program
    {
        public static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            var cin = new Scanner();
            int n = cin.NextInt();
            int m = cin.NextInt();
            int x = cin.NextInt() - 1;
            int y = cin.NextInt() - 1;
            var dijk = new Dijkstra(n);
            var p = new List<int>();
            var q = new List<int>();
            for (int i = 0; i < n; i++)
            {
                p.Add(cin.NextInt());
                q.Add(cin.NextInt());
            }
            for (int i = 0; i < m; i++)
            {
                var pp = cin.NextInt() - 1;
                var qq = cin.NextInt() - 1;
                dijk.AddPath(pp, qq,
                    Math.Sqrt((p[pp] - p[qq]) * (p[pp] - p[qq]) + (q[pp] - q[qq]) * (q[pp] - q[qq])));
            }
            if (p[x] == p[y] && q[x] == q[y]) Console.WriteLine(0);
            else Console.WriteLine(dijk.GetMinCost(x, y));
            Console.Out.Flush();
        }
    }
    /// <summary>
    /// Get min cost between two points
    /// </summary>
    public class Dijkstra
    {
        private int maxIndex = -1;
        private const int INF = Int32.MaxValue;
        private double[,] _edgeArray;
        /// <summary>
        /// Dijkstra, get min cost between two points
        /// should not contain negatie cost path
        /// </summary>
        /// <param name="size">max index of vertices</param>
        public Dijkstra(int size)
        {
            maxIndex = size + 1;
            _edgeArray = new double[maxIndex, maxIndex];
            for (int i = 0; i < _edgeArray.GetLength(0); i++)
            {
                for (int j = 0; j < _edgeArray.GetLength(1); j++)
                {
                    _edgeArray[i, j] = INF;
                    if (i == j) _edgeArray[i, j] = 0;
                }
            }
        }
        // Add a path(no direction) with its cost
        public void AddPath(int s, int t, double cost)
        {
            _edgeArray[s, t] = Math.Min(_edgeArray[s, t], cost);
            _edgeArray[t, s] = _edgeArray[s, t];
        }
        //Get the min cost between s and t
        //return Int32.MaxValue if no path
        public double GetMinCost(int s, int t)
        {
            double[] cost = new double[maxIndex];
            for (int i = 0; i < cost.Length; i++) cost[i] = INF;
            cost[s] = 0;
            var priorityQueue = new PriorityQueue<Pair<double, int>>(maxIndex);
            priorityQueue.Push(new Pair<double, int>(0, s));
            while (priorityQueue.Count() > 0)
            {
                var costDestinationPair = priorityQueue.Pop();
                if (cost[costDestinationPair.Second] < costDestinationPair.First) continue;
                for (int i = 0; i < maxIndex; i++)
                {
                    double newCostToi = _edgeArray[costDestinationPair.Second, i] == INF ? INF :
                        costDestinationPair.First + _edgeArray[costDestinationPair.Second, i];
                    if (newCostToi < cost[i])
                    {
                        cost[i] = newCostToi;
                        priorityQueue.Push(new Pair<double, int>(newCostToi, i));
                    }
                }
            }
            return cost[t];
        }
    }
    public class Pair<T, U> : IComparable, IEquatable<Pair<T, U>> where T : IComparable<T>, IEquatable<T> where U : IComparable<U>, IEquatable<U>
    {
        public T First { get; set; }
        public U Second { get; set; }
        public Pair(T first, U second)
        {
            First = first;
            Second = second;
        }
        public int CompareTo(object obj)
        {
            Pair<T, U> castedObj = (Pair<T, U>)obj;
            int x = First.CompareTo(castedObj.First);
            if (x != 0) return x;
            else return Second.CompareTo(castedObj.Second);
        }
        public static bool operator ==(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == 0;
        public static bool operator !=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) != 0;
        public static bool operator <(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == 1;
        public static bool operator >(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == -1;
        public static bool operator <=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) > 0;
        public static bool operator >=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) < 0;
        public bool Equals(Pair<T, U> x) => First.Equals(x.First) && Second.Equals(x.Second);
        public override bool Equals(object obj)
        {
            return obj is Pair<T, U> pair &&
                   EqualityComparer<T>.Default.Equals(First, pair.First) &&
                   EqualityComparer<U>.Default.Equals(Second, pair.Second);
        }
        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = 405212230;
                hashCode = hashCode * -1521134295 + EqualityComparer<T>.Default.GetHashCode(First);
                hashCode = hashCode * -1521134295 + EqualityComparer<U>.Default.GetHashCode(Second);
                return hashCode;
            }
        }
    }
    public class PriorityQueue<T> where T : IComparable
    {
        private IComparer<T> _comparer = null;
        private int _type = 0;
        private T[] _heap;
        private int _sz = 0;
        private int _count = 0;
        /// <summary>
        /// Priority Queue with custom comparer
        /// </summary>
        public PriorityQueue(int maxSize, IComparer<T> comparer)
        {
            _heap = new T[maxSize];
            _comparer = comparer;
        }
        /// <summary>
        /// Priority queue
        /// </summary>
        /// <param name="maxSize">max size</param>
        /// <param name="type">0: asc, 1:desc</param>
        public PriorityQueue(int maxSize, int type = 0)
        {
            _heap = new T[maxSize];
            _type = type;
        }
        private int Compare(T x, T y)
        {
            if (_comparer != null) return _comparer.Compare(x, y);
            return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
        }
        public void Push(T x)
        {
            _count++;
            //node number
            var i = _sz++;
            while (i > 0)
            {
                //parent node number
                var p = (i - 1) / 2;
                if (Compare(_heap[p], x) <= 0) break;
                _heap[i] = _heap[p];
                i = p;
            }
            _heap[i] = x;
        }
        public T Pop()
        {
            _count--;
            T ret = _heap[0];
            T x = _heap[--_sz];
            int i = 0;
            while (i * 2 + 1 < _sz)
            {
                //children
                int a = i * 2 + 1;
                int b = i * 2 + 2;
                if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;
                if (Compare(_heap[a], x) >= 0) break;
                _heap[i] = _heap[a];
                i = a;
            }
            _heap[i] = x;
            return ret;
        }
        public int Count()
        {
            return _count;
        }
        public T Peek()
        {
            return _heap[0];
        }
        public bool Contains(T x)
        {
            for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
            return false;
        }
        public void Clear()
        {
            while (this.Count() > 0) this.Pop();
        }
        public IEnumerator<T> GetEnumerator()
        {
            var ret = new List<T>();
            while (this.Count() > 0)
            {
                ret.Add(this.Pop());
            }
            foreach (var r in ret)
            {
                this.Push(r);
                yield return r;
            }
        }
        public T[] ToArray()
        {
            T[] array = new T[_sz];
            int i = 0;
            foreach (var r in this)
            {
                array[i++] = r;
            }
            return array;
        }
    }
    class Scanner
    {
        string[] s;
        int i;
        char[] cs = new char[] { ' ' };
        public Scanner()
        {
            s = new string[0];
            i = 0;
        }
        public string Next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return Next();
            i = 0;
            return s[i++];
        }
        public int NextInt()
        {
            return int.Parse(Next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextInt() + add;
            }
            return Array;
        }
        public long NextLong()
        {
            return long.Parse(Next());
        }
        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextLong() + add;
            }
            return Array;
        }
        public double NextDouble()
        {
            return double.Parse(Next());
        }
        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextDouble() + add;
            }
            return Array;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0