結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー fairy_lettucefairy_lettuce
提出日時 2020-05-30 00:04:51
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 767 ms / 2,000 ms
コード長 7,819 bytes
コンパイル時間 2,395 ms
コンパイル使用メモリ 108,672 KB
実行使用メモリ 53,968 KB
最終ジャッジ日時 2024-04-24 02:45:53
合計ジャッジ時間 16,593 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
18,816 KB
testcase_01 AC 31 ms
18,944 KB
testcase_02 AC 392 ms
40,188 KB
testcase_03 AC 517 ms
53,844 KB
testcase_04 AC 515 ms
53,696 KB
testcase_05 AC 382 ms
53,700 KB
testcase_06 AC 384 ms
53,836 KB
testcase_07 AC 138 ms
30,720 KB
testcase_08 AC 452 ms
53,152 KB
testcase_09 AC 66 ms
24,832 KB
testcase_10 AC 212 ms
37,108 KB
testcase_11 AC 154 ms
31,996 KB
testcase_12 AC 125 ms
30,208 KB
testcase_13 AC 411 ms
41,256 KB
testcase_14 AC 477 ms
47,320 KB
testcase_15 AC 548 ms
50,120 KB
testcase_16 AC 273 ms
35,840 KB
testcase_17 AC 596 ms
51,992 KB
testcase_18 AC 200 ms
31,744 KB
testcase_19 AC 559 ms
50,436 KB
testcase_20 AC 171 ms
31,360 KB
testcase_21 AC 236 ms
35,712 KB
testcase_22 AC 517 ms
48,440 KB
testcase_23 AC 35 ms
20,096 KB
testcase_24 AC 36 ms
19,968 KB
testcase_25 AC 116 ms
29,824 KB
testcase_26 AC 311 ms
37,628 KB
testcase_27 AC 306 ms
37,248 KB
testcase_28 AC 515 ms
46,024 KB
testcase_29 AC 85 ms
26,240 KB
testcase_30 AC 550 ms
49,572 KB
testcase_31 AC 390 ms
42,068 KB
testcase_32 AC 256 ms
35,708 KB
testcase_33 AC 548 ms
48,552 KB
testcase_34 AC 207 ms
32,000 KB
testcase_35 AC 552 ms
49,968 KB
testcase_36 AC 33 ms
19,584 KB
testcase_37 AC 35 ms
19,668 KB
testcase_38 AC 33 ms
19,328 KB
testcase_39 AC 35 ms
19,536 KB
testcase_40 AC 31 ms
19,328 KB
testcase_41 AC 767 ms
53,968 KB
testcase_42 AC 223 ms
32,252 KB
testcase_43 AC 398 ms
40,952 KB
testcase_44 AC 148 ms
29,312 KB
testcase_45 AC 387 ms
40,436 KB
testcase_46 AC 26 ms
17,920 KB
testcase_47 AC 31 ms
18,816 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++)
            {
                int pp = cin.NextInt() - 1;
                int qq = cin.NextInt() - 1;
                dijk.Add(pp, qq, GetLength(p[pp], q[pp], p[qq], q[qq]));
            }
            if (p[x] == p[y] && q[x] == q[y]) Console.WriteLine(0);
            else Console.WriteLine(dijk.GetMinCost(x)[y]);

            Console.Out.Flush();
        }

        public static double GetLength(double x1, double y1, double x2, double y2)
            => Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

    }

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

    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 * 2];
            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