#488736 (C#(csc)) No.1065 電柱 / Pole (Easy)

提出ソース

結果

問題	No.1065 電柱 / Pole (Easy)
ユーザー	fairy_lettuce
提出日時	2020-05-29 22:07:22
言語	C#(csc) (csc 3.9.0)
結果	RE
実行時間	-
コード長	9,582 bytes
コンパイル時間	1,052 ms
コンパイル使用メモリ	118,640 KB
実行使用メモリ	534,432 KB
最終ジャッジ日時	2024-04-23 22:41:40
合計ジャッジ時間	5,805 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	26 ms 32,212 KB
testcase_01	AC	26 ms 23,092 KB
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	MLE	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

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;
		}
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード