結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 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());}}