結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー fairy_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39 RE * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0