結果

問題 No.5007 Steiner Space Travel
ユーザー RisenRisen
提出日時 2022-07-30 15:26:54
言語 C#
(.NET 8.0.203)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 187 ms
49,684 KB
testcase_01 AC 208 ms
51,104 KB
testcase_02 AC 193 ms
53,244 KB
testcase_03 AC 198 ms
53,120 KB
testcase_04 AC 181 ms
50,668 KB
testcase_05 AC 170 ms
49,004 KB
testcase_06 AC 191 ms
52,484 KB
testcase_07 AC 193 ms
52,428 KB
testcase_08 AC 225 ms
53,288 KB
testcase_09 AC 175 ms
49,472 KB
testcase_10 AC 186 ms
51,356 KB
testcase_11 AC 191 ms
51,212 KB
testcase_12 AC 185 ms
50,572 KB
testcase_13 AC 183 ms
50,612 KB
testcase_14 AC 181 ms
50,056 KB
testcase_15 AC 216 ms
53,364 KB
testcase_16 AC 205 ms
52,644 KB
testcase_17 AC 194 ms
52,256 KB
testcase_18 AC 190 ms
51,828 KB
testcase_19 AC 204 ms
52,504 KB
testcase_20 AC 195 ms
50,588 KB
testcase_21 AC 185 ms
51,392 KB
testcase_22 AC 194 ms
49,820 KB
testcase_23 AC 193 ms
51,712 KB
testcase_24 AC 189 ms
51,396 KB
testcase_25 AC 180 ms
49,608 KB
testcase_26 AC 185 ms
51,364 KB
testcase_27 AC 185 ms
51,080 KB
testcase_28 AC 191 ms
52,048 KB
testcase_29 AC 192 ms
188,092 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  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);
    }

    //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());
    }
}
0