using System; using System.Collections.Generic; using System.Linq; using System.Diagnostics; using System.Text; using static Constants; using static Common; public static class Common { public static void Swap(ref T lhs, ref T rhs) { T temp = lhs; lhs = rhs; rhs = temp; } } 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; } namespace Edmonds { public enum TreeLevel { EVEN, ODD, DUMBBELL } public class Blossom { public Blossom() { charge = 0; treeLevel = TreeLevel.EVEN; treeParentBlossom = null; treeParentEdge = null; outwardBlossom = null; } public double Charge => charge; public TreeLevel TreeLevel => treeLevel; public void AddCharge(double delta) { charge += delta; UpdateVertexTotal(delta); } public void UpdateCharge(double reserve) { if (TreeLevel == TreeLevel.EVEN) { AddCharge(reserve); } else { AddCharge(-reserve); } foreach (var child in treeChildren) { child.UpdateCharge(reserve); } } public Blossom GetOutermostBlossom() { Blossom outermost = this; while (outermost.outwardBlossom != null) { outermost = outermost.outwardBlossom; } return outermost; } public Blossom GetInnerBlossomContaining(Vertex v) { Blossom inner = v; while (inner != null && inner.outwardBlossom != this) { inner = inner.outwardBlossom; } return inner; } public Blossom GetRootBlossom() { Blossom root = this; while (root.treeParentBlossom != null) { root = root.treeParentBlossom; } return root; } public virtual Vertex GetStem() { return innerChildren[0].GetStem(); } public void FlipPathAndDisassemble(Vertex v, Blossom pair = null, Edge pairEdge = null) { Vertex v2 = GetStem(); if (TreeLevel == TreeLevel.ODD) { v2 = treeParentEdge.V1; if (v2.GetOutermostBlossom() != this) { v2 = treeParentEdge.V2; } } FlipPathBetween(v, v2); if (TreeLevel == TreeLevel.EVEN) { foreach (var child in treeChildren) { if (child != pair) { child.DisassembleTreeIntoDumbbells(); } } } treeChildren.Clear(); Blossom parent = treeParentBlossom; Edge parentEdge = treeParentEdge; treeParentBlossom = null; treeParentEdge = null; TreeLevel oldTreeLevel = TreeLevel; if (pair != null) { MakeDumbbellWith(pair, pairEdge); } if (parent == null) { return; } Vertex pv = parentEdge.V1; if (pv.GetOutermostBlossom() == this) { pv = parentEdge.V2; } parentEdge.Flip(); if (oldTreeLevel == TreeLevel.EVEN) { parent.FlipPathAndDisassemble(pv); } else { parent.FlipPathAndDisassemble(pv, this, parentEdge); } } public void DisassembleTreeIntoDumbbells() { if (TreeLevel == TreeLevel.EVEN) { foreach (var child in treeChildren) { child.DisassembleTreeIntoDumbbells(); } treeChildren.Clear(); treeParentBlossom = null; treeParentEdge = null; } else { Blossom pair = treeChildren.First.Value; Edge pairEdge = treeChildren.First.Value.treeParentEdge; pair.DisassembleTreeIntoDumbbells(); treeChildren.Clear(); treeParentBlossom = null; treeParentEdge = null; MakeDumbbellWith(pair, pairEdge); } } public void FlipPathBetween(Vertex v1, Vertex v2) { if (GetStem() != v1) { Swap(ref v1, ref v2); } if (innerChildren.Count == 0) { return; } Blossom b2 = GetInnerBlossomContaining(v2); Blossom first = innerChildren[0]; Blossom last = b2; int pos = innerChildren.FindIndex(c => c == b2); if (pos % 2 == 1) { Swap(ref v1, ref v2); Swap(ref first, ref last); } Blossom current = first; while (current != last) { Vertex b_v1 = current.nextBlossomEdge.V1; Vertex b_v2 = current.nextBlossomEdge.V2; if (GetInnerBlossomContaining(b_v1) != current) { Swap(ref b_v1, ref b_v2); } current.FlipPathBetween(v1, b_v1); current.nextBlossomEdge.Flip(); current = GetInnerBlossomContaining(b_v2); v1 = b_v2; } last.FlipPathBetween(v1, v2); innerChildren = innerChildren.Skip(pos).Concat(innerChildren.Take(pos)).ToList(); } public void MakeDumbbellWith(Blossom pair, Edge edge) { this.treeLevel = TreeLevel.DUMBBELL; pair.treeLevel = TreeLevel.DUMBBELL; this.treeParentBlossom = pair; pair.treeParentBlossom = this; this.treeParentEdge = edge; pair.treeParentEdge = edge; } public void ConnectToTree(Blossom parent, Edge parentEdge) { treeLevel = TreeLevel.ODD; treeChildren.AddLast(treeParentBlossom); treeParentBlossom.treeLevel = TreeLevel.EVEN; treeParentBlossom = parent; treeParentEdge = parentEdge; treeParentBlossom.treeChildren.AddLast(this); } public Blossom MakeBlossomWith(Blossom pair, Edge pairEdge) { LinkedList ourPath = new LinkedList(); LinkedList pairPath = new LinkedList(); ourPath.AddLast(this); pairPath.AddLast(pair); while (ourPath.Last.Value.treeParentBlossom != null) { ourPath.AddLast(ourPath.Last.Value.treeParentBlossom); } while (pairPath.Last.Value.treeParentBlossom != null) { pairPath.AddLast(pairPath.Last.Value.treeParentBlossom); } Blossom LCA = null; while (ourPath.Count > 0 && pairPath.Count > 0 && ourPath.Last.Value == pairPath.Last.Value) { LCA = ourPath.Last.Value; ourPath.RemoveLast(); pairPath.RemoveLast(); } Blossom newBlossom = new Blossom { treeParentBlossom = LCA.treeParentBlossom, treeParentEdge = LCA.treeParentEdge }; if (newBlossom.treeParentBlossom != null) { newBlossom.treeParentBlossom.treeChildren.Remove(LCA); newBlossom.treeParentBlossom.treeChildren.AddLast(newBlossom); } newBlossom.innerChildren.Add(LCA); Blossom previous = LCA; foreach (var p in ourPath.Reverse()) { newBlossom.innerChildren.Add(p); previous.nextBlossomEdge = p.treeParentEdge; previous = p; } previous.nextBlossomEdge = pairEdge; foreach (var p in pairPath) { newBlossom.innerChildren.Add(p); p.nextBlossomEdge = p.treeParentEdge; } foreach (var inner in newBlossom.innerChildren) { inner.outwardBlossom = newBlossom; } foreach (var inner in newBlossom.innerChildren) { foreach (var child in inner.treeChildren) { if (child.outwardBlossom == null) { newBlossom.treeChildren.AddLast(child); child.treeParentBlossom = newBlossom; } } } newBlossom.outwardBlossom = null; if (LCA.treeParentEdge == null) { return newBlossom; } return null; } public void DisassembleBlossom() { Edge childEdge = treeChildren.First.Value.treeParentEdge; Blossom parentInner; if (treeParentEdge.V1.GetOutermostBlossom() == this) { parentInner = GetInnerBlossomContaining(treeParentEdge.V1); } else { parentInner = GetInnerBlossomContaining(treeParentEdge.V2); } int pos = innerChildren.FindIndex(c => c == parentInner); int N = innerChildren.Count; int start = 0; int end = pos; int diff = 1; int ediff = 0; int stem = 0; if (pos % 2 == 1) { start = pos; end = stem = N; diff = ediff = -1; } for (int i = start; i <= end; i++) { innerChildren[i % N].treeLevel = (i % 2 == stem % 2) ? TreeLevel.ODD : TreeLevel.EVEN; innerChildren[i % N].treeParentBlossom = (i == pos) ? treeParentBlossom : innerChildren[i + diff]; innerChildren[i % N].treeParentEdge = (i == pos) ? treeParentEdge : innerChildren[i + ediff].nextBlossomEdge; innerChildren[i % N].treeChildren.Clear(); innerChildren[i % N].treeChildren.AddLast((i == stem) ? treeChildren.First.Value : innerChildren[(i - diff) % N]); } treeParentBlossom.treeChildren.Remove(this); treeParentBlossom.treeChildren.AddLast(innerChildren[pos]); treeChildren.First.Value.treeParentBlossom = innerChildren[0]; Blossom thiscopy = innerChildren[0].outwardBlossom; foreach (var inner in innerChildren) { inner.outwardBlossom = null; } for (int i = (pos % 2 == 0) ? pos + 1 : 1; (pos % 2 == 0) ? i < N : i < pos; i += 2) { innerChildren[i].treeChildren.Clear(); innerChildren[i + 1].treeChildren.Clear(); innerChildren[i].treeParentBlossom = null; innerChildren[i + 1].treeParentBlossom = null; innerChildren[i].MakeDumbbellWith(innerChildren[i + 1], innerChildren[i].nextBlossomEdge); } } public virtual double GetMaxNegativeCharge() { return Charge; } public bool UpdateTree() { foreach (var child in treeChildren) { if (child.UpdateTree()) { return true; } } if (GetMaxNegativeCharge() == 0 && TreeLevel == TreeLevel.ODD) { DisassembleBlossom(); return true; } return false; } public virtual void UpdateVertexTotal(double delta) { foreach (var inner in innerChildren) { inner.UpdateVertexTotal(delta); } } private double charge; private TreeLevel treeLevel; private Blossom treeParentBlossom; private Edge treeParentEdge; private LinkedList treeChildren = new LinkedList(); private Blossom outwardBlossom; private List innerChildren = new List(); private Edge nextBlossomEdge; } public class Vertex : Blossom { public Vertex(int _id) : base() { this.id = _id; this.totalCharge = 0; } public double TotalCharge => totalCharge; public override double GetMaxNegativeCharge() { return double.PositiveInfinity; } public override void UpdateVertexTotal(double delta) { totalCharge += delta; } public override Vertex GetStem() { return this; } public readonly int id; private double totalCharge; } public class Edge { public Edge(EdmondsMatching edmondsMatching, Vertex v1, Vertex v2, double weight) { this.edmondsMatching = edmondsMatching; this.v1 = v1; this.v2 = v2; this.weight = weight; this.matched = false; } public Vertex V1 => v1; public Vertex V2 => v2; public double GetMaxCharge() { var outer1 = v1.GetOutermostBlossom(); var outer2 = v2.GetOutermostBlossom(); if (outer1 == outer2) { return double.PositiveInfinity; } double reserve = weight - v1.TotalCharge - v2.TotalCharge; if (IsBetweenDumbbells(outer1, outer2)) { return double.PositiveInfinity; } if (IsBetweenEvenAndDumbbell(outer1, outer2)) { return reserve; } if (IsBetweenEvenBlossoms(outer1, outer2)) { return reserve / 2; } reserve = double.PositiveInfinity; if (outer1.TreeLevel == TreeLevel.ODD) { reserve = Math.Min(reserve, outer1.GetMaxNegativeCharge()); } if (outer2.TreeLevel == TreeLevel.ODD) { reserve = Math.Min(reserve, outer2.GetMaxNegativeCharge()); } return reserve; } public bool Update() { if (GetMaxCharge() > 0) { return false; } var outer1 = v1.GetOutermostBlossom(); var outer2 = v2.GetOutermostBlossom(); if (IsBetweenEvenAndDumbbell(outer1, outer2)) { if (outer1.TreeLevel == TreeLevel.DUMBBELL) { outer1.ConnectToTree(outer2, this); } else { outer2.ConnectToTree(outer1, this); } return true; } if (IsBetweenEvenBlossoms(outer1, outer2)) { var root1 = outer1.GetRootBlossom(); var root2 = outer2.GetRootBlossom(); if (root1 == root2) { Blossom newRoot = outer1.MakeBlossomWith(outer2, this); if (newRoot != null) { edmondsMatching.RemoveRootFromForest(root1); edmondsMatching.AddRootToForest(newRoot); } } else { outer1.FlipPathAndDisassemble(v1); outer2.FlipPathAndDisassemble(v2); edmondsMatching.RemoveRootFromForest(root1); edmondsMatching.RemoveRootFromForest(root2); outer1.MakeDumbbellWith(outer2, this); this.Flip(); edmondsMatching.IncreaseMatchingSize(); } return true; } return true; } public void Flip() { matched = !matched; } public bool IsMatched() { return matched; } public double GetWeight() { return weight; } private EdmondsMatching edmondsMatching; private Vertex v1; private Vertex v2; private double weight; private bool matched; private bool IsBetweenDumbbells(Blossom outer1, Blossom outer2) { return (outer1.TreeLevel == TreeLevel.DUMBBELL && outer2.TreeLevel == TreeLevel.DUMBBELL); } private bool IsBetweenEvenBlossoms(Blossom outer1, Blossom outer2) { return (outer1.TreeLevel == TreeLevel.EVEN && outer2.TreeLevel == TreeLevel.EVEN); } private bool IsBetweenEvenAndDumbbell(Blossom outer1, Blossom outer2) { return ((outer1.TreeLevel == TreeLevel.DUMBBELL && outer2.TreeLevel == TreeLevel.EVEN) || (outer1.TreeLevel == TreeLevel.EVEN && outer2.TreeLevel == TreeLevel.DUMBBELL)); } } public class EdmondsMatching { public EdmondsMatching(int numberOfVertices) { this.numberOfVertices = numberOfVertices; this.matchingSize = 0; vertices.Capacity = numberOfVertices; for (int i = 0; i < numberOfVertices; i++) { vertices.Add(new Vertex(i)); roots.AddLast(vertices[vertices.Count - 1]); } } public void AddEdge(int v1id, int v2id, double weight) { Vertex v1 = vertices[v1id]; Vertex v2 = vertices[v2id]; edges.Add(new Edge(this, v1, v2, weight)); } public bool FindMinimumWeightMatching() { while (true) { double min_reserve = double.PositiveInfinity; foreach (var edge in edges) { double edge_reserve = edge.GetMaxCharge(); min_reserve = Math.Min(min_reserve, edge_reserve); } foreach (var root in roots) { root.UpdateCharge(min_reserve); } bool change = false; while (true) { bool round = false; foreach (var root in roots) { if (root.UpdateTree()) { round = change = true; break; } } if (round) { continue; } foreach (var edge in edges) { if (edge.Update()) { round = change = true; break; } } if (round) { continue; } break; } if (!change && min_reserve == 0) { return false; } if (matchingSize * 2 == numberOfVertices) { return true; } if (min_reserve == double.PositiveInfinity) { return false; } } } public void RemoveRootFromForest(Blossom root) { roots.Remove(root); } public void AddRootToForest(Blossom root) { roots.AddLast(root); } public void IncreaseMatchingSize() { matchingSize += 1; } public double GetMatchingWeight() { double weight = 0; foreach (var edge in edges) { if (edge.IsMatched()) { weight += edge.GetWeight(); } } return weight; } public List> GetMatchedEdges() { return edges.Where(e => e.IsMatched()).Select(e => Tuple.Create(e.V1.id, e.V2.id)).ToList(); } private int matchingSize; private int numberOfVertices; private List vertices = new List(); private List edges = new List(); private LinkedList roots = new LinkedList(); } } public class PriorityQueue { SortedDictionary> dict = new SortedDictionary>(); int count; public int Count { get { return count; } } public void Enqueue(TKey key, TValue value) { Stack set; if (!dict.TryGetValue(key, out set)) { set = new Stack(); dict[key] = set; } set.Push(value); count++; } public KeyValuePair Dequeue() { var queue = dict.First(); if (queue.Value.Count <= 1) { dict.Remove(queue.Key); } var val = queue.Value.Pop(); count--; return new KeyValuePair(queue.Key, val); } public KeyValuePair Peek() { var queue = dict.First(); var val = queue.Value.Peek(); return new KeyValuePair(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 struct Edge { public readonly int Start; public readonly int End; public readonly double Weight; public Edge(int v0, int v1, double w) { Start = v0; End = v1; Weight = w; } public override string ToString() { return $"{Start} {End} {Weight}"; } } public class Graph { // Prim法により最小全域木を求める public static List[] GetMinSpanningTree(Edge[][] edges, int startVertex = 0) { var treeEdges = Enumerable.Range(0, edges.Length).Select(_ => new List()).ToArray(); var treeVertex = new HashSet() { startVertex }; var nearEdges = new PriorityQueue(); foreach (var e in edges[startVertex]) { nearEdges.Enqueue(e.Weight, e); } while (nearEdges.Count > 0) { var edge = nearEdges.Dequeue().Value; if (treeVertex.Contains(edge.End)) { continue; } treeEdges[edge.Start].Add(edge); treeEdges[edge.End].Add(new Edge(edge.End, edge.Start, edge.Weight)); treeVertex.Add(edge.End); foreach (var e in edges[edge.End]) { nearEdges.Enqueue(e.Weight, e); } } return treeEdges; } // Edmondsの花分解により最小重み完全マッチングを求める public static List GetMinWeightMatching(Edge[][] edges, IList vertexes) { var n = vertexes.Count; var matching = new Edmonds.EdmondsMatching(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { continue; } matching.AddEdge(i, j, edges[vertexes[i]][vertexes[j]].Weight); } } matching.FindMinimumWeightMatching(); var minEdges = matching.GetMatchedEdges(); return minEdges.Select(e => edges[vertexes[e.Item1]][vertexes[e.Item2]]).ToList(); } // オイラー路を求める graphは消去される public static List EulerTour(List[] graph, int current = 0) { var path = new List { current }; if (graph[current].Count == 1) { while (graph[current].Count == 1) { var next = graph[current].First().End; graph[current].RemoveAt(0); graph[next].Remove(graph[next].First(e => e.End == current)); path.Add(next); current = next; } } if (graph[current].Count > 1) { var pathToEnd = new List(); while (graph[current].Count > 0) { var next = graph[current].First().End; graph[current].RemoveAt(0); graph[next].Remove(graph[next].First(e => e.End == current)); var nextPath = EulerTour(graph, next); if (nextPath.Last() != current) { pathToEnd = nextPath; } else { path.AddRange(nextPath); } } path.AddRange(pathToEnd); } return path; } } public class Solver { public Point[] Planets; public Point[] Stations; public List Way; public Stopwatch Sw; Random Random = new Random(); public Solver(Point[] planets, Stopwatch sw) { Planets = planets; Stations = new Point[M]; Sw = sw; } 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(); 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); } (long[][] distance, int[][] prevs) CalcAllDistance() { var distance = new long[N + M][]; var prevs = new int[N + M][]; for (int i = 0; i < N + M; i++) { (distance[i], prevs[i]) = Dijkstra(i); } return (distance, prevs); } void InitStations() { { 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); } } } } public void SolveByNearestNeighbor() { InitStations(); 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() { 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(); 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(); for (int i = 0; i != last; i = prev[i]) { way.Push(i); } foreach (var i in way) { path.Add(i); } } Way = path; } public void Solve() { InitStations(); InitCost(); (var distance, var prevs) = CalcAllDistance(); var edges = Enumerable.Range(0, N).Select(_ => new Edge[N]).ToArray(); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { var d = distance[i][j]; edges[i][j] = new Edge(i, j, d); edges[j][i] = new Edge(j, i, d); } } var mst = Graph.GetMinSpanningTree(edges); var oddVertexes = Enumerable.Range(0, edges.Length).Where(i => mst[i].Count % 2 == 1).ToList(); var minMatches = Graph.GetMinWeightMatching(edges, oddVertexes); var graph = mst; foreach (var e in minMatches) { graph[e.Start].Add(e); graph[e.End].Add(new Edge(e.End, e.Start, e.Weight)); } var eulerCycle = Graph.EulerTour(graph); //Optimize(edges, ref eulerCycle); var path = new List() { 0 }; for (int t = 0; t < eulerCycle.Count - 1; t++) { var u = eulerCycle[t]; var v = eulerCycle[t + 1]; var way = new Stack(); for (int i = v; i != u; i = prevs[u][i]) { way.Push(i); } foreach (var i in way) { path.Add(i); } } Way = path; } public void Optimize(Edge[][] edges, ref List path) { const int limit = 900; long lap = 500; var update = true; while (update) { if (Sw.ElapsedMilliseconds + lap > limit) { break; } update = false; var t0 = Sw.ElapsedMilliseconds; TwoOpt(edges, ref path); update = ThreeOpt(edges, ref path); var t1 = Sw.ElapsedMilliseconds; lap = t1 - t0; } } public static bool TwoOpt(Edge[][] edges, ref List path) { bool result = false; var ps = path; Func distance = (s, e) => { return edges[ps[s]][ps[e]].Weight; }; var n = path.Count; bool updated = true; while (updated) { updated = false; for (int i = 0; i < n - 2; i++) { for (int j = i + 2; j < n - 1; j++) { if (distance(i, i + 1) + distance(j, j + 1) > distance(i, j) + distance(i + 1, j + 1)) { // i+1 <= x <= j を逆順にする var a = ps.Take(i + 1); var b = ps.Skip(i + 1).Take(j - i).Reverse(); var c = ps.Skip(j + 1); ps = a.Concat(b).Concat(c).ToList(); updated = true; result = true; } } } } path = ps; return result; } public static bool ThreeOpt(Edge[][] edges, ref List path) { bool result = false; var ps = path; Func distance = (s, e) => { return edges[ps[s]][ps[e]].Weight; }; var n = path.Count; start: for (int i = 0; i < n - 3; i++) { for (int j = i + 1; j < n - 2; j++) { for (int k = j + 1; k < n - 1; k++) { var d = new double[5]; d[0] = distance(i, i + 1) + distance(j, j + 1) + distance(k, k + 1); // original d[1] = distance(i, j) + distance(i + 1, k) + distance(j + 1, k + 1); d[2] = distance(i, j + 1) + distance(k, j) + distance(i + 1, k + 1); d[3] = distance(i, j + 1) + distance(k, i + 1) + distance(j, k + 1); d[4] = distance(i, k) + distance(j + 1, i + 1) + distance(j, k + 1); var min = d.Min(); var minCase = Array.IndexOf(d, min); if (minCase == 0) { continue; } switch (minCase) { case 1: ps = ps.Take(i + 1).Concat(ps.Take(j + 1).Skip(i + 1).Reverse()).Concat(ps.Take(k + 1).Skip(j + 1).Reverse()).Concat(ps.Skip(k + 1)).ToList(); break; case 2: ps = ps.Take(i + 1).Concat(ps.Take(k + 1).Skip(j + 1)).Concat(ps.Take(j + 1).Skip(i + 1).Reverse()).Concat(ps.Skip(k + 1)).ToList(); break; case 3: ps = ps.Take(i + 1).Concat(ps.Take(k + 1).Skip(j + 1)).Concat(ps.Take(j + 1).Skip(i + 1)).Concat(ps.Skip(k + 1)).ToList(); break; case 4: ps = ps.Take(i + 1).Concat(ps.Take(k + 1).Skip(j + 1).Reverse()).Concat(ps.Take(j + 1).Skip(i + 1)).Concat(ps.Skip(k + 1)).ToList(); break; } result = true; goto start; } } } path = ps; return result; } 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 sw = Stopwatch.StartNew(); var solver = new Solver(points, sw); solver.Solve(); Console.Write(solver.GetAnswer()); } }