結果

問題 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/

ソースコード

diff #
プレゼンテーションモードにする

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);
}
//objtrue
public override bool Equals(object obj)
{
if (!(obj is Point))
{
return false;
}
Point p = (Point)obj;
return (X == p.X && Y == p.Y);
}
//Equalstrue
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());
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0