結果
| 問題 | No.1065 電柱 / Pole (Easy) |
| ユーザー |
 Yusei Kato
|
| 提出日時 | 2020-06-26 11:15:01 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,633 bytes |
| コンパイル時間 | 1,358 ms |
| コンパイル使用メモリ | 68,392 KB |
| 実行使用メモリ | 655,228 KB |
| 最終ジャッジ日時 | 2023-09-16 23:37:59 |
| 合計ジャッジ時間 | 15,906 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 71 ms
27,112 KB |
| testcase_01 | AC | 72 ms
25,188 KB |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | TLE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | AC | 1,860 ms
39,324 KB |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | MLE | - |
| 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 | -- | - |
ソースコード
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
namespace Problem1065
{
public class PriorityQueue<T> : IEnumerable<T>
{
private readonly List<T> _data;
private readonly IComparer<T> _comparer;
private readonly bool _isAscending;
private int Count { get; set; }
public int GetCount()
{
return Count;
}
public PriorityQueue(IComparer<T> comparer, bool isAscending = true)
{
_data = new List<T>();
_comparer = comparer;
_isAscending = isAscending;
}
public PriorityQueue() : this (Comparer<T>.Default)
{
_data = new List<T>();
_isAscending = true;
}
public void Enqueue(T item)
{
_data.Add(item);
Count++;
var childIndex = _data.Count - 1;
while (childIndex > 0)
{
var parentIndex = (childIndex - 1) / 2;
if (Compare(_data[childIndex], _data[parentIndex]) <= 0)
{
break;
}
Swap(childIndex, parentIndex);
childIndex = parentIndex;
}
}
public T Dequeue()
{
var res = _data[0];
_data[0] = _data[_data.Count - 1];
_data.RemoveAt(_data.Count - 1);
Count--;
var parentIndex = 0;
while ((parentIndex + 1) * 2 <= _data.Count)
{
var childIndex1 = (parentIndex + 1) * 2 - 1;
if (childIndex1 + 1 == _data.Count)
{
if (Compare(_data[childIndex1], _data[parentIndex]) >= 0)
{
break;
}
Swap(childIndex1, parentIndex);
parentIndex = childIndex1;
}
else
{
var childIndex2 = childIndex1 + 1;
int childIndex;
childIndex = Compare(_data[childIndex1], _data[childIndex2]) >= 0 ? childIndex2 : childIndex1;
if (Compare(_data[childIndex], _data[parentIndex]) >= 0)
{
break;
}
Swap(childIndex, parentIndex);
parentIndex = childIndex;
}
}
return res;
}
public T Peek() => _data[0];
public IEnumerator<T> GetEnumerator() => _data.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
private int Compare(T a, T b)
{
return _isAscending ? _comparer.Compare(a, b) : _comparer.Compare(b, a);
}
private void Swap(int index1, int index2)
{
T temp;
temp = _data[index1];
_data[index1] = _data[index2];
_data[index2] = temp;
}
}
class Program
{
static void Main(string[] args)
{
var buff = GetLongArray();
long N = buff[0];
long M = buff[1];
buff = GetLongArray();
long start = buff[0];
long goal = buff[1];
var position = new long[N][];
for(int i = 0; i < N; i++)
{
position[i] = GetLongArray();
}
var wire = new long[M][];
for (int i = 0; i < M; i++)
{
wire[i] = GetLongArray();
}
var edge = new double[N, N];
for(int i = 0; i < M; i++)
{
SearchIni(wire[i], edge, position);
}
Console.WriteLine(BFS(edge, goal - 1, start - 1));
}
public static void SearchIni(long[] raw, double[,] edge, long[][] position)
{
double distance = Math.Pow(Math.Pow(position[raw[0] - 1][0] - position[raw[1] - 1][0], 2) + Math.Pow(position[raw[0] - 1][1] - position[raw[1] - 1][1], 2), 0.5);
if (distance == 0)
{
edge[raw[0] - 1, raw[1] - 1] = -1;
edge[raw[1] - 1, raw[0] - 1] = -1;
}
else
{
edge[raw[0] - 1, raw[1] - 1] = distance;
edge[raw[1] - 1, raw[0] - 1] = distance;
}
}
public static double BFS(double[,] edge, long goal, long start)
{
var queue = new PriorityQueue<long>();
queue.Enqueue(start);
var distance = new double[edge.GetLength(0)];
for (int i = 0; i < distance.Length; i++)
{
distance[i] = double.MaxValue;
}
distance[start] = 0;
var searched = new HashSet<long>();
while(queue.GetCount() != 0)
{
var current = queue.Dequeue();
searched.Add(current);
for(int i = 0; i < edge.GetLength(0); i++)
{
if(edge[current, i] != 0 && !searched.Contains(i))
{
queue.Enqueue(i);
double temp = distance[current] + edge[current, i];
distance[i] = distance[i] > temp ? temp : distance[i];
}
}
}
return distance[goal];
}
public static long[] GetLongArray() => Console.ReadLine().Split().Select(long.Parse).ToArray();
}
}