結果
| 問題 | No.1065 電柱 / Pole (Easy) |
| ユーザー |
 fairy_lettuce
|
| 提出日時 | 2020-05-29 22:21:54 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 9,716 bytes |
| コンパイル時間 | 1,212 ms |
| コンパイル使用メモリ | 116,368 KB |
| 実行使用メモリ | 693,436 KB |
| 最終ジャッジ日時 | 2024-11-06 05:30:28 |
| 合計ジャッジ時間 | 5,984 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 31 ms
33,884 KB |
| testcase_01 | AC | 30 ms
25,000 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.
ソースコード
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;
private int translate(int x, int y) => x + maxIndex * y;
/// <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[translate(maxIndex, maxIndex)];
for (int i = 0; i < maxIndex; i++)
{
for (int j = 0; j < maxIndex; j++)
{
_edgeArray[translate(i, j)] = INF;
if (i == j) _edgeArray[translate(i, j)] = 0;
}
}
}
// Add a path(no direction) with its cost
public void AddPath(int s, int t, double cost)
{
_edgeArray[translate(s,t )] = Math.Min(_edgeArray[translate(s,t )], cost);
_edgeArray[translate(t, s)] = _edgeArray[translate(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[translate(costDestinationPair.Second, i)] == INF ? INF :
costDestinationPair.First + _edgeArray[translate(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;
}
}
}