graph_III_1

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

namespace graph_1
{
    public class Graph
    {
        private class Node
        {
            private int[,] array;
            private bool[] nov;
            private string[] names;

            public int this[int i, int j]
            {
                get { return array[i, j]; }
                set { array[i, j] = value; }
            }

            public string this[int i]
            {
                get { return names[i]; }
            }

            public int Size
            {
                get { return array.GetLength(0); }
            }

            public void NovSet()
            {
                for (int i = 0; i < Size; i++)
                    nov[i] = true;
            }

            public Node(int[,] tmp, string[] names)
            {
                array = tmp;
                nov = new bool[tmp.GetLength(0)];
                this.names = names;
            }

            public int[,] SearchShortestWayByCities(string A, string B, string[] cities)
            {
                int indexA = 0;
                int indexB = 0;
                List<int> indexofcities = new List<int>();
                for (int i = 0; i < names.Length; i++)
                {
                    if (names[i] == A)
                    {
                        indexA = i;
                    }
                    else if (names[i] == B)
                    {
                        indexB = i;
                    }
                    else for (int j = 0; j < cities.Length; j++)
                            if (names[i] == cities[j])
                                indexofcities.Add(i);
                }

                int[,] newarray = new int[Size, Size];
                bool flag = true;
                for (int i = 0; i < Size; i++)
                    for (int j = 0; j < Size; j++)
                    {
                        flag = true;
                        for (int k = 0; k < indexofcities.Count; k++)
                            if (i == indexofcities[k] || j == indexofcities[k])
                            {
                                newarray[i, j] = array[i, j];
                                flag = false;
                            }
                        if (flag) newarray[i, j] = 0;
                    }
                return newarray;
            }

            //реализация алгоритма Флойда
            public long[,] Floyd(out int[,] p, int[,] tmp)
            {
                int i, j, k;
                long[,] a = new long[Size, Size];
                p = new int[Size, Size];

                for (i = 0; i < Size; i++)
                    for (j = 0; j < Size; j++)
                    {
                        if (i == j) a[i, j] = 0;
                        else
                        {
                            if (tmp[i, j] == 0)
                                a[i, j] = int.MaxValue;
                            else a[i, j] = tmp[i, j];
                        }
                        p[i, j] = -1;
                    }

                for (k = 0; k < Size; k++)
                    for (i = 0; i < Size; i++)
                        for (j = 0; j < Size; j++)
                        {
                            long distance = a[i, k] + a[k, j];
                            if (a[i, j] > distance)
                            {
                                a[i, j] = distance;
                                p[i, j] = k;
                            }
                        }

                return a;//в качестве результата возвращается массив кратчайших путей между
            }

            public void WayFloyd(int a, int b, int[,] p, ref Queue<int> items)
            {
                int k = p[a, b];
                if (k != -1)
                {

                    WayFloyd(a, k, p, ref items);
                    items.Enqueue(k);
                    WayFloyd(k, b, p, ref items);
                }
            }
        }
        private Node graph;

        public Graph(string nameOfFile)
        {
            StreamReader fin = new StreamReader(nameOfFile);
            int n = int.Parse(fin.ReadLine());
            string[] names = fin.ReadLine().Split(' ');
            int[,] tmp = new int[n, n];
            for (int i = 0; i < n; i++)
            {
                string[] arr = fin.ReadLine().Split(' ');
                for (int j = 0; j < n; j++)
                    tmp[i, j] = int.Parse(arr[j]);
            }
            graph = new Node(tmp, names);
        }

        public void SearchShortestWayByCities()
        {
            int [,]p;
            Console.WriteLine("Введите название города, из кторого необходимо найти кратчайший путь: ");
            string a = Console.ReadLine();
            Console.WriteLine("Введите название города, в который необходимо найти кратчайший путь: ");
            string b = Console.ReadLine();

            Console.WriteLine("Введите названия городов, через которые необходимо проложить путь: ");
            string [] cities = Console.ReadLine().Split(' ');
            int[,] newarray = graph.SearchShortestWayByCities(a, b, cities);
            long [,] tmp = graph.Floyd(out p, newarray);

            int indexA = 0;
            int indexB = 0;
            for (int i = 0; i < graph.Size; i++)
            {
                if (graph[i] == a)
                    indexA = i;
                else if (graph[i] == b)
                    indexB = i;
            }

            if (tmp[indexA,indexB]==int.MaxValue)
                Console.WriteLine("Пути из вершины {0} в вершину {1} не существует", graph[indexA], graph[indexB]);
            else
            {
                Console.WriteLine("Кратчайший путь от вершины {0} до вершины {1} равен {2}, ", graph[indexA], graph[indexB], tmp[indexA, indexB]);

                Console.Write("Путь: ");
                Queue<int> items = new Queue<int>();
                items.Enqueue(indexA);
                graph.WayFloyd(indexA, indexB, p, ref items);
                items.Enqueue(indexB);
                while (items.Count != 0)
                    Console.Write("{0} ", graph[items.Dequeue()]);
                Console.WriteLine ();
            }
        }
    }



    class Program
    {
        static void Main(string[] args)
        {
            Graph graph1 = new Graph("input.txt");
            graph1.SearchShortestWayByCities();
        }
    }
}

//input
5
Березовка Еремеевка Октябрьское Рузаевка Сосновка
0 70 0 0 20
70 0 75 25 15
0 75 0 40 60
0 25 40 0 0
20 15 60 0 0