Яндекс.Блиц. D

D_Graph.cs

// https://contest.yandex.ru/hiring/contest/5048/problems/D/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace yandex.blitz
{
    public class D_Graph
    {
        struct City
        {
            public int X;
            public int Y;

            public int Distance(City other)
            {
                return Math.Abs(X - other.X) + Math.Abs(Y - other.Y);
            }
        }


        public static void Main(string[] args)
        {
            var cities = new List<City>();
            int n, minDist, from, to;

            using (var file = new System.IO.StreamReader("input.txt"))
            {
                n = int.Parse(file.ReadLine());
                for (int i = 0; i < n; i++)
                {
                    var values = file.ReadLine().Split(' ');
                    cities.Add(new City() { X = int.Parse(values[0]), Y = int.Parse(values[1]) });
                }

                minDist = int.Parse(file.ReadLine());
                var path = file.ReadLine().Split(' ');
                from = int.Parse(path[0]) - 1;
                to = int.Parse(path[1]) - 1;
            }

            if (n < 2 || n > 1000 || from < 0 || from > (n - 1))
            {
                using (var file = new System.IO.StreamWriter("output.txt"))
                {
                    file.WriteLine(-1);
                }
                return;
            }

            Graph g = new Graph();
            for (int i = 0; i < n; i++)
            {
                var edges = new Dictionary<int, int>();
                for (int j = 0; j < n; j++)
                {
                    if (i == j) continue;

                    int dist = cities[i].Distance(cities[j]);
                    if (dist > minDist)
                    {
                        continue;
                    }
                    edges[j] = 1; // = dist
                }
                g.addVertex(i, edges);
            }

            var shortestPath = g.ShortestPath(from, to);

            using (var file = new System.IO.StreamWriter("output.txt"))
            {
                if (null == shortestPath)
                {
                    file.WriteLine(-1);
                }
                else
                {
                    file.WriteLine(shortestPath.Count);
                }
            }
        }

        class Graph
        {
            Dictionary<int, Dictionary<int, int>> vertices = new Dictionary<int, Dictionary<int, int>>();

            public void addVertex(int name, Dictionary<int, int> edges)
            {
                vertices[name] = edges;
            }

            public List<int> ShortestPath(int start, int finish)
            {
                var previous = new Dictionary<int, int>();
                var distances = new Dictionary<int, int>();
                var nodes = new List<int>();

                List<int> path = null;

                foreach (var vertex in vertices)
                {
                    if (vertex.Key == start)
                    {
                        distances[vertex.Key] = 0;
                    }
                    else
                    {
                        distances[vertex.Key] = int.MaxValue;
                    }

                    nodes.Add(vertex.Key);
                }

                while (nodes.Count != 0)
                {
                    nodes.Sort((x, y) => distances[x] - distances[y]);

                    var smallest = nodes[0];
                    nodes.Remove(smallest);

                    if (smallest == finish)
                    {
                        path = new List<int>();
                        while (previous.ContainsKey(smallest))
                        {
                            path.Add(smallest);
                            smallest = previous[smallest];
                        }

                        break;
                    }

                    if (distances[smallest] == int.MaxValue)
                    {
                        break;
                    }

                    foreach (var neighbor in vertices[smallest])
                    {
                        var alt = distances[smallest] + neighbor.Value;
                        if (alt < distances[neighbor.Key])
                        {
                            distances[neighbor.Key] = alt;
                            previous[neighbor.Key] = smallest;
                        }
                    }
                }

                return path;
            }
        }
    }
}