Submission #587280

---

Source Code Expand

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

namespace G
{
    class Program
    {
        static void Main(string[] args)
        {

            int N, M;
            var items = Console.ReadLine().Split(' ');
            N = int.Parse(items[0]);
            M = int.Parse(items[1]);

            var lines = new string[M];
            for (int m = 0; m < M; m++)
            {
                lines[m] = Console.ReadLine();
            }
            //int N = 6, M = 7;
            //var lines = new string[] {
            //    "1 2 1 6",
            //    "1 3 7 4",
            //    "2 3 3 4",
            //    "2 5 6 6",
            //    "3 4 4 6",
            //    "3 5 1 3",
            //    "5 6 2 4"

            //};



            var ways =new Way   [M];
            for (int m = 0; m < M; m++)
            {
                ways[m] = new Way(lines[m]);
            }
            var wayDic = new Dictionary<int, List<Way>>();
            for (int n = 0; n < N; n++)
            {
                wayDic[n] = new List<Way>();
            }
            foreach (var way in ways)
            {
                wayDic[way.a].Add(way);
                wayDic[way.b].Add(way);
            }


            Dictionary<int, long>[] minTimes = new Dictionary<int, long>[N];
            HashSet<int>[] changed = new  HashSet<int> [N];
            for (int i = 0; i < N; i++)
            {
                changed[i] = new  HashSet<int>();   
                minTimes[i] = new Dictionary<int, long>();

                foreach (var way in wayDic[i])
                {
                    minTimes[i][way.c] = long.MaxValue/2;
                }
            }


            minTimes[0][1] = 0;
            changed[0].Add(1);
            bool loop = true;
            while (loop)
            {
                loop = false;


                for (int n = 0; n < N; n++)
                {
                    var changedColors = changed[n];
                    changed[n] = new  HashSet<int>();
                    foreach (var color in changedColors)
                    {
                        foreach (var way in wayDic[n])
                        {
                            int n2 = way.a == n ? way.b : way.a;
                            long nextTime = minTimes[n][color] + Math.Abs(color - way.c) + way.t;
                            if (minTimes[n2][way.c] > nextTime)
                            {
                                minTimes[n2][way.c] = nextTime;
                                changed[n2].Add(way.c);
                                loop = true;
                            }
                            //Console.WriteLine("{0} {1}", n, n2);
                        }
                    }
                }
            }

            long  result = minTimes[N - 1].Values.Min();

            Console.WriteLine(result);


        }



        class Way
        {
            public Way(string line)
            {
                var items = line.Split(' ');
                a = int.Parse(items[0])-1;
                b = int.Parse(items[1])-1;
                c = int  .Parse(items[2]);
                t = long .Parse(items[3]);

            }

            public int a;
            public int b;
            public int  c;
            public long  t;
        }

    }
}

Submission Info

Judge Result