結果
| 問題 |
No.5007 Steiner Space Travel
|
| ユーザー |
 Risen
|
| 提出日時 | 2022-07-30 15:26:54 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 225 ms / 1,000 ms |
| コード長 | 7,743 bytes |
| コンパイル時間 | 8,022 ms |
| 実行使用メモリ | 188,092 KB |
| スコア | 7,623,753 |
| 最終ジャッジ日時 | 2022-07-30 15:27:11 |
| 合計ジャッジ時間 | 14,082 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 143 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Text;
using static Constants;
public static class Constants
{
public const int N = 100;
public const int M = 8;
public const int UniverseSize = 1000;
public const int Alpha = 5;
public const int TypePlanet = 1;
public const int TypeStation = 2;
}
public class PriorityQueue<TKey, TValue>
{
SortedDictionary<TKey, Stack<TValue>> dict = new SortedDictionary<TKey, Stack<TValue>>();
int count;
public int Count
{
get
{
return count;
}
}
public void Enqueue(TKey key, TValue value)
{
Stack<TValue> set;
if (!dict.TryGetValue(key, out set))
{
set = new Stack<TValue>();
dict[key] = set;
}
set.Push(value);
count++;
}
public KeyValuePair<TKey, TValue> Dequeue()
{
var queue = dict.First();
if (queue.Value.Count <= 1)
{
dict.Remove(queue.Key);
}
var val = queue.Value.Pop();
count--;
return new KeyValuePair<TKey, TValue>(queue.Key, val);
}
public KeyValuePair<TKey, TValue> Peek()
{
var queue = dict.First();
var val = queue.Value.Peek();
return new KeyValuePair<TKey, TValue>(queue.Key, val);
}
}
public struct Point
{
public int X;
public int Y;
public Point(Point p)
{
X = p.X;
Y = p.Y;
}
public Point(int x, int y)
{
X = x;
Y = y;
}
public static bool operator ==(Point a, Point b)
{
return (a.X == b.X && a.Y == b.Y);
}
public static bool operator !=(Point a, Point b)
{
return !(a == b);
}
//objと自分自身が等価のときはtrueを返す
public override bool Equals(object obj)
{
if (!(obj is Point))
{
return false;
}
Point p = (Point)obj;
return (X == p.X && Y == p.Y);
}
//Equalsがtrueを返すときに同じ値を返す
public override int GetHashCode()
{
return (X << 16) ^ Y;
}
public Point Clone()
{
return new Point(X, Y);
}
public void Reverse()
{
X = -X;
Y = -Y;
}
public static Point operator +(Point a, Point b)
{
return new Point(a.X + b.X, a.Y + b.Y);
}
public static Point operator -(Point a, Point b)
{
return new Point(a.X - b.X, a.Y - b.Y);
}
public static Point operator *(Point a, int i)
{
return new Point(a.X * i, a.Y * i);
}
public static Point operator /(Point a, int i)
{
return new Point(a.X / i, a.Y / i);
}
public static Point operator +(Point a)
{
return new Point(+a.X, +a.Y);
}
public static Point operator -(Point a)
{
return new Point(-a.X, -a.Y);
}
public override string ToString()
{
return string.Format("({0},{1})", X, Y);
}
public string AsAnswer()
{
return string.Format("{0} {1}", X, Y);
}
public int Norm2()
{
return X * X + Y * Y;
}
public int Distance2(Point that)
{
return (that - this).Norm2();
}
}
public class Solver
{
public Point[] Planets;
public Point[] Stations;
public List<int> Way;
Random Random = new Random();
public Solver(Point[] planets)
{
Planets = planets;
Stations = new Point[M];
}
Point GetPoint(int id)
{
if (id < N)
{
return Planets[id];
}
return Stations[id - N];
}
long[,] Cost;
void InitCost()
{
Cost = new long[N + M, N + M];
for (int i = 0; i < N + M; i++)
{
for (int j = i + 1; j < N + M; j++)
{
var c = CalcCost(i, j);
Cost[i, j] = Cost[j, i] = c;
}
}
}
long CalcCost(int start, int goal)
{
var cost = GetPoint(start).Distance2(GetPoint(goal));
if (start < N)
{
cost *= Alpha;
}
if (goal < N)
{
cost *= Alpha;
}
return cost;
}
(long[] distance, int[] prev) Dijkstra(int start)
{
var d = new long[N + M];
Array.Fill(d, long.MaxValue);
var prev = new int[N + M];
d[start] = 0;
var q = new PriorityQueue<long, int>();
q.Enqueue(0, start);
while (q.Count > 0)
{
var t = q.Dequeue();
var u = t.Value;
if (t.Key > d[u])
{
continue;
}
for (int v = 0; v < N + M; v++)
{
if (u == v)
{
continue;
}
var len = Cost[u, v];
if (len == int.MaxValue)
{
continue;
}
if (d[v] > d[u] + len)
{
d[v] = d[u] + len;
q.Enqueue(d[v], v);
prev[v] = u;
}
}
}
return (d, prev);
}
public void Solve()
{
{
var d = UniverseSize / 6;
var i = 0;
for (int y = 0; y < 3; y++)
{
for (int x = 0; x < 3; x++)
{
if (x == 1 && y == 1)
{
continue;
}
Stations[i++] = new Point(d + d * 2 * x, d + d * 2 * y);
}
}
}
InitCost();
var distance = new long[N + M][];
var prevs = new int[N + M][];
var remain = Enumerable.Range(1, N + M - 1).ToList();
var path = new List<int>() { 0 };
while (remain.Count > 0)
{
var last = path.Last();
(var d, var prev) = Dijkstra(last);
var min = remain.OrderBy(i => d[i]).First();
var way = new Stack<int>();
for (int i = min; i != last; i = prev[i])
{
way.Push(i);
}
foreach (var i in way)
{
path.Add(i);
}
remain.Remove(min);
}
{
var last = path.Last();
(var d, var prev) = Dijkstra(last);
var way = new Stack<int>();
for (int i = 0; i != last; i = prev[i])
{
way.Push(i);
}
foreach (var i in way)
{
path.Add(i);
}
}
Way = path;
}
public string GetAnswer()
{
var buff = new StringBuilder();
foreach (var p in Stations)
{
buff.AppendLine(p.AsAnswer());
}
buff.AppendLine(Way.Count.ToString());
foreach (var i in Way)
{
var type = i < N ? TypePlanet : TypeStation;
var index = (i < N ? i : i - N) + 1;
buff.AppendLine($"{type} {index}");
}
return buff.ToString();
}
}
public static class Solution
{
public static void Main()
{
var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
var points = new Point[N];
for (int i = 0; i < N; i++)
{
vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
points[i] = new Point(vals[0], vals[1]);
}
var solver = new Solver(points);
solver.Solve();
Console.Write(solver.GetAnswer());
}
}