結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー fairy_lettucefairy_lettuce
提出日時 2020-05-30 00:04:51
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 706 ms / 2,000 ms
コード長 7,819 bytes
コンパイル時間 2,763 ms
コンパイル使用メモリ 115,032 KB
実行使用メモリ 63,672 KB
最終ジャッジ日時 2024-11-06 09:32:10
合計ジャッジ時間 17,577 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
23,220 KB
testcase_01 AC 31 ms
25,020 KB
testcase_02 AC 352 ms
46,440 KB
testcase_03 AC 489 ms
62,928 KB
testcase_04 AC 495 ms
61,148 KB
testcase_05 AC 374 ms
61,540 KB
testcase_06 AC 373 ms
61,816 KB
testcase_07 AC 135 ms
34,960 KB
testcase_08 AC 446 ms
63,672 KB
testcase_09 AC 66 ms
32,936 KB
testcase_10 AC 211 ms
41,308 KB
testcase_11 AC 148 ms
37,840 KB
testcase_12 AC 123 ms
38,544 KB
testcase_13 AC 390 ms
49,384 KB
testcase_14 AC 452 ms
53,256 KB
testcase_15 AC 513 ms
57,580 KB
testcase_16 AC 251 ms
44,028 KB
testcase_17 AC 572 ms
61,460 KB
testcase_18 AC 188 ms
39,876 KB
testcase_19 AC 525 ms
58,400 KB
testcase_20 AC 150 ms
39,184 KB
testcase_21 AC 214 ms
44,052 KB
testcase_22 AC 467 ms
56,560 KB
testcase_23 AC 36 ms
25,156 KB
testcase_24 AC 35 ms
24,900 KB
testcase_25 AC 112 ms
35,900 KB
testcase_26 AC 269 ms
43,880 KB
testcase_27 AC 275 ms
43,396 KB
testcase_28 AC 461 ms
55,872 KB
testcase_29 AC 80 ms
34,444 KB
testcase_30 AC 509 ms
55,664 KB
testcase_31 AC 356 ms
49,960 KB
testcase_32 AC 235 ms
41,664 KB
testcase_33 AC 500 ms
56,308 KB
testcase_34 AC 187 ms
40,284 KB
testcase_35 AC 501 ms
53,856 KB
testcase_36 AC 32 ms
23,092 KB
testcase_37 AC 33 ms
24,984 KB
testcase_38 AC 33 ms
25,036 KB
testcase_39 AC 35 ms
25,132 KB
testcase_40 AC 32 ms
25,024 KB
testcase_41 AC 706 ms
61,936 KB
testcase_42 AC 204 ms
40,256 KB
testcase_43 AC 353 ms
49,144 KB
testcase_44 AC 135 ms
33,568 KB
testcase_45 AC 349 ms
46,440 KB
testcase_46 AC 28 ms
24,308 KB
testcase_47 AC 32 ms
26,788 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