結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー fairy_lettucefairy_lettuce
提出日時 2020-05-29 22:49:11
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 9,627 bytes
コンパイル時間 4,602 ms
コンパイル使用メモリ 116,248 KB
実行使用メモリ 63,248 KB
最終ジャッジ日時 2024-11-06 06:56:40
合計ジャッジ時間 16,896 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
25,036 KB
testcase_01 AC 32 ms
22,968 KB
testcase_02 AC 385 ms
46,444 KB
testcase_03 AC 511 ms
62,104 KB
testcase_04 AC 503 ms
62,044 KB
testcase_05 AC 388 ms
63,248 KB
testcase_06 AC 381 ms
60,936 KB
testcase_07 AC 141 ms
39,444 KB
testcase_08 AC 459 ms
59,336 KB
testcase_09 AC 66 ms
30,636 KB
testcase_10 AC 208 ms
43,208 KB
testcase_11 AC 155 ms
40,896 KB
testcase_12 AC 123 ms
36,256 KB
testcase_13 AC 395 ms
49,244 KB
testcase_14 AC 461 ms
55,428 KB
testcase_15 AC 552 ms
56,436 KB
testcase_16 RE -
testcase_17 AC 595 ms
59,712 KB
testcase_18 RE -
testcase_19 AC 550 ms
58,544 KB
testcase_20 AC 165 ms
37,788 KB
testcase_21 RE -
testcase_22 AC 513 ms
52,752 KB
testcase_23 AC 36 ms
24,692 KB
testcase_24 AC 36 ms
25,032 KB
testcase_25 AC 117 ms
36,024 KB
testcase_26 AC 304 ms
45,800 KB
testcase_27 AC 307 ms
45,700 KB
testcase_28 AC 510 ms
54,148 KB
testcase_29 RE -
testcase_30 AC 558 ms
57,544 KB
testcase_31 AC 396 ms
50,168 KB
testcase_32 AC 255 ms
39,864 KB
testcase_33 RE -
testcase_34 AC 204 ms
35,680 KB
testcase_35 AC 556 ms
55,904 KB
testcase_36 RE -
testcase_37 AC 37 ms
24,908 KB
testcase_38 AC 36 ms
26,948 KB
testcase_39 AC 37 ms
24,988 KB
testcase_40 RE -
testcase_41 AC 768 ms
59,888 KB
testcase_42 AC 221 ms
41,040 KB
testcase_43 AC 402 ms
49,160 KB
testcase_44 AC 145 ms
38,312 KB
testcase_45 AC 382 ms
46,340 KB
testcase_46 AC 27 ms
21,816 KB
testcase_47 AC 32 ms
26,920 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Add(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();
        }
	}

    class Dijkstra
    {
        public int N { get; set; }
        public List<Edge>[] G { get; set; }
        public Dijkstra(int n)
        {
            this.N = n;
            this.G = new List<Edge>[N];
            for (int i = 0; i < N; i++)
            {
                this.G[i] = new List<Edge>();
            }
        }
        // a から b につながる辺を追加する
        public void Add(int a, int b, double cost = 1)
        {
            this.G[a].Add(new Edge(b, cost));
            this.G[b].Add(new Edge(a, cost));
        }

        // 単一始点の最短経路を求める
        public double[] GetMinCost(int start)
        {
            // 最短経路(コスト)を格納しておく配列(すべての頂点の初期値をINFにしておく)
            var cost = new double[N];
            for (int i = 0; i < N; i++) cost[i] = double.MaxValue;
            cost[start] = 0;

            // 未確定の頂点を格納する優先度付きキュー(頂点とコストを格納)
            var q = new PriorityQueue<P>(this.N, false);
            q.Enqueue(new P(start, 0));

            // 未確定の頂点があればすべて確認する
            while (q.Count > 0)
            {
                var p = q.Dequeue();
                // すでに記録されているコストと異なる(より大きい)場合、無視する。
                if (p.Cost != cost[p.A]) continue;

                // 取り出した頂点を確定する。
                // 確定した頂点から直接辺でつながる頂点をループ
                foreach (var e in this.G[p.A])
                {
                    // すでに記録されているコストより小さいコストの場合
                    if (cost[e.To] > p.Cost + e.Cost)
                    {
                        // コストを更新して、候補としてキューに入れる
                        cost[e.To] = p.Cost + e.Cost;
                        q.Enqueue(new P(e.To, cost[e.To]));
                    }
                }
            }

            return cost;
        }

        // 接続先の頂点とコストを格納する辺のデータ
        public struct Edge
        {
            public int To;
            public double Cost;
            public Edge(int to, double cost)
            {
                this.To = to;
                this.Cost = cost;
            }
        }
        // 頂点とその頂点までのコストを記録
        public struct P : IComparable<P>
        {
            public int A;
            public double Cost;
            public P(int a, double cost)
            {
                this.A = a;
                this.Cost = cost;
            }
            public int CompareTo(P other)
            {
                return this.Cost.CompareTo(other.Cost);
            }
        }
    }

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

    class PriorityQueue<T> where T : IComparable<T>
    {
        public readonly T[] Array;
        public readonly bool Greater;
        public int Count { get; private set; } = 0;

        public PriorityQueue(int capacity, bool greater = true)
        {
            this.Array = new T[capacity];
            this.Greater = greater;
        }

        public void Enqueue(T item)
        {
            this.Array[this.Count] = item;
            this.Count += 1;
            this.UpHeap();
        }

        public T Dequeue()
        {
            // 先頭要素を末尾にして再構成
            this.Swap(0, this.Count - 1);
            this.Count -= 1;
            this.DownHeap();

            return this.Array[this.Count];
        }


        private void UpHeap()
        {
            var n = this.Count - 1;
            while (n != 0)
            {
                // 親要素の座標
                var parent = (n - 1) / 2;

                if (this.Compare(this.Array[n], this.Array[parent]) > 0)
                {
                    this.Swap(n, parent);
                    n = parent;
                }
                else
                {
                    break;
                }
            }
        }

        private void DownHeap()
        {
            var parent = 0;
            while (true)
            {
                var child = 2 * parent + 1;
                if (child > this.Count - 1) break;

                if (child < this.Count - 1 && this.Compare(this.Array[child], this.Array[child + 1]) < 0)
                {
                    // 左より右の子のほうが大きい値の場合、右を入れ替え対象にする
                    child += 1;
                }

                if (this.Compare(this.Array[parent], this.Array[child]) < 0)
                {
                    this.Swap(parent, child);
                    parent = child;
                }
                else
                {
                    break;
                }
            }
        }

        private int Compare(T a, T b)
        {
            var c = a.CompareTo(b);
            if (!this.Greater)
            {
                c = -c;
            }
            return c;
        }

        private void Swap(int a, int b)
        {
            var tmp = this.Array[a];
            this.Array[a] = this.Array[b];
            this.Array[b] = tmp;
        }
    }

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