using System;
using System.IO;

public class Proj5
{
    public static string[] cities;
    public static int[,] mileage;
    public static bool[] visited;
    public static int[] prev;
    public static int[] dist;
    public static int size;

    public static void Main()
    {
        //should read the input file, create the arrays,
        //get pairs of cities from the user, and call
        //appropriate methods to get the value of the shortest path
        Console.Write("Enter the name of the input file: ");
        string filename = Console.ReadLine();

        StreamReader sr = new StreamReader(filename);
        int size = Convert.ToInt32(sr.ReadLine());
        cities = new string[size];
        mileage = new int[size, size];

        sr.ReadLine();
        for (int i = 0; i < size; i++)
        {
            cities = sr.ReadLine();
        }
        sr.ReadLine();

        for (int i = 0; i < size; i++)
        {
            string cur = sr.ReadLine();
            while (cur != "" && cur != null)
            {
                char[] delim = { ',', ':' };
                string[] tokens = cur.Split(delim);

                int j = 0;
                for (; j < size; j++)
                {
                    if (cities[j] == tokens[1]) break;
                }
                mileage[i, j] = Convert.ToInt32(tokens[2]);
                cur = sr.ReadLine();
            }
        }
        sr.Close();

        string cont = "Y";
        do
        {
            Console.Write("\nEnter the first city: ");
            string city1 = Console.ReadLine();
            Console.Write("Enter the second city: ");
            string city2 = Console.ReadLine();
            
            Proj5.print(city1,city2);
            
            Console.Write("\nAnother pair? (Y/N): ");
            cont = Console.ReadLine();
        } while (cont == "Y" || cont == "y");
        

    }

    public static int index(string name)
    {
        //should return the index of name in the cities array
        for (int i = 0; i < cities.Length; i++)
        {
            if (cities == name) return i;
        }
        return -1;
    }

    public static void init(string start)
    {
        //should initialize the values in the dist and prev arrays
        //start is the name of the starting city
        for (int i = 0; i < dist.Length; i++)
        {
            dist = -1;
            prev = -1;
            visited = false;
        }
        int startIndex = Proj5.index(start);
        dist[startIndex] = 0;
    }

    public static int minIndex()
    {
        //should return the index of the unvisited city
        //with minimum dist

        int lowest = dist[0];
        for (int i = 0; i < dist.Length; i++)
        {
            if (lowest > dist && dist <= 0 && visited == false)
            {
                lowest = i;
            }
        }
        return lowest;
    }

    public static bool done()
    {
        //returns whether all cities have been visited

        return false;
    }

    public static void print(string start, string stop)
    {
        //prints the shortest path from start city
        //to stop city, plus the total distance

        int index1 = -1;
        int index2 = -1;
        for (int i = 0; i < cities.Length; i++)
        {
            if (start == cities) index1 = i;
            if (stop == cities) index2 = i;
        }

        if (index1 == -1 || index2 == -1)
        {
            Console.WriteLine("\nInvalid city name(s)");
        }
        else
        {
            Console.WriteLine("\n" + start + "->" + stop + ", distance " + mileage[index1, index2] + " miles");
        }

    }

    public static void dijkstra(string start)
    {
        //implements dijkstra's algorithm starting at start city
        //call the init, minIndex, and done methods to help you

        Proj5.init(start);
        Proj5.minIndex();
        Proj5.done();
        bool done = false;

        while(done == false)
        {
            int x = Proj5.minIndex();
            visited[x] = true;
            for (int i = 0; i < cities.Length; i++)
            {
                if (visited == false)
                {
                    if (mileage[x, i] != 0)
                    {
                        int dy = dist[x] + mileage[x, i];
                        if (dy < dist)
                        {
                            dist = dy;
                            prev = x;
                        }
                    }
                }
            }
            done = Proj5.done();
        }
    }
}