Submission #1690000


Source Code Expand

using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace NotFounds
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve();
        }

        public void Solve()
        {
            var cin = new MyInputStream();
            var N = cin.ReadInt();
            var graph = new Graph(N);
            for (int i = 0; i < N - 1; ++i)
            {
                var a = cin.ReadInt() - 1;
                var b = cin.ReadInt() - 1;
                var c = cin.ReadInt();
                graph.AddUnDirectedEdge(a, b, c);
            }
            var Q = cin.ReadInt();
            var K = cin.ReadInt() - 1;
            var dist = graph.Dijkstra(K);
            for (int i = 0; i < Q; ++i)
            {
                var x = cin.ReadInt() - 1;
                var y = cin.ReadInt() - 1;
                //Console.Error.WriteLine($"{x} -> {K} : {dist[x]}");
                //Console.Error.WriteLine($"{y} -> {K} : {dist[y]}");
                WriteLine(dist[x] + dist[y]);
            }
        }

        private static void PrintYN(bool b)
        {
            //WriteLine(b ? "YES" : "NO");
            WriteLine(b ? "Yes" : "No");
        }
    }

    public class Graph
    {
        private struct Edge
        {
            public int To;
            public long Cost;
            public Edge(int t, long c)
            {
                this.To = t;
                this.Cost = c;
            }
        }

        private struct Node : IComparable<Node>
        {
            public int Pos;
            public long Cost;
            public Node(int p, long c)
            {
                this.Pos = p;
                this.Cost = c;
            }
            public int CompareTo(Node obj)
            {
                return (int)(this.Cost - obj.Cost);
            }
        }

        private List<List<Edge>> g;
        private int N { get; set; }
        public Graph(int size)
        {
            N = size;
            g = new List<List<Edge>>(size);
            for (int i = 0; i < size; i++) g.Add(new List<Edge>());
        }

        public List<long> Dijkstra(int start = 0)
        {
            long Inf = long.MaxValue >> 1;
            var q = new PriorityQueue<Node>();
            q.Enqueue(new Node(start, 0));
            var ret = new List<long>(N);
            for (int i = 0; i < N; i++) ret.Add(Inf);

            while (q.Any())
            {
                var tmp = q.Dequeue();
                if (ret[tmp.Pos] == Inf) ret[tmp.Pos] = tmp.Cost;
                else continue;

                foreach (var e in g[tmp.Pos])
                    q.Enqueue(new Node(e.To, e.Cost + tmp.Cost));
            }

            return ret;
        }

        // If result is null, g has a negative cycle.
        public List<long> BellmanFord(int start = 0)
        {
            long Inf = long.MaxValue >> 1;
            var ret = new List<long>(N);
            for (int i = 0; i < N; i++) ret.Add(Inf);
            ret[start] = 0;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    for (int k = 0; k < g[j].Count(); k++)
                    {
                        var e = g[j][k];
                        if (ret[j] != Inf && ret[e.To] > ret[j] + e.Cost)
                        {
                            ret[e.To] = ret[j] + e.Cost;
                            if (i == N - 1) return null;
                        }
                    }
                }
            }

            return ret;
        }

        public void AddDirectedEdge(int from, int to, long cost)
        {
            g[from].Add(new Edge(to, cost));
        }

        public void AddUnDirectedEdge(int from, int to, int cost)
        {
            AddDirectedEdge(from, to, cost);
            AddDirectedEdge(to, from, cost);
        }
    }

    public class PriorityQueue<T> : IEnumerable<T>, ICollection, IEnumerable
    {
        private Comparison<T> comp;
        private List<T> list;
        private int count;
        public int Count { get { return count; } }
        public bool IsEmpty { get { return count == 0; } }
        public PriorityQueue(IComparer<T> comp) : this((x, y) => comp.Compare(x, y)) { }
        public PriorityQueue(IComparer<T> comp, int capacity) : this((x, y) => comp.Compare(x, y), capacity) { }
        public PriorityQueue(IComparer<T> comp, IEnumerable<T> source) : this((x, y) => comp.Compare(x, y), source) { }
        public PriorityQueue(IComparer<T> comp, int capacity, IEnumerable<T> source) : this((x, y) => comp.Compare(x, y), source) { list.Capacity = capacity; }
        public PriorityQueue() : this((x, y) => ((IComparable<T>)x).CompareTo(y)) { }
        public PriorityQueue(int capacity) : this((x, y) => ((IComparable<T>)x).CompareTo(y), capacity) { }
        public PriorityQueue(IEnumerable<T> source) : this((x, y) => ((IComparable<T>)x).CompareTo(y), source) { }
        public PriorityQueue(int capacity, IEnumerable<T> source) : this((x, y) => ((IComparable<T>)x).CompareTo(y), source) { list.Capacity = capacity; }
        public PriorityQueue(Comparison<T> comparison)
        {
            comp = comparison;
            list = new List<T>();
            count = 0;
        }
        public PriorityQueue(Comparison<T> comparison, IEnumerable<T> source) : this(comparison) { foreach (var x in source) Enqueue(x); }
        public PriorityQueue(Comparison<T> comparison, int capacity) : this(comparison) { list.Capacity = capacity; }
        public void Enqueue(T x) // O(log n)
        {
            var pos = count++;
            list.Add(x);
            while (pos > 0)
            {
                var p = (pos - 1) / 2;
                if (comp(list[p], x) <= 0) break;
                list[pos] = list[p];
                pos = p;
            }
            list[pos] = x;
        }
        public T Dequeue() // O(log n)
        {
            if (count == 0) throw new InvalidOperationException();
            var value = list[0];
            var x = list[--count];
            list.RemoveAt(count);
            if (count == 0) return value;
            var pos = 0;
            while (pos * 2 + 1 < count)
            {
                var a = 2 * pos + 1;
                var b = 2 * pos + 2;
                if (b < count && comp(list[b], list[a]) < 0) a = b;
                if (comp(list[a], x) >= 0) break;
                list[pos] = list[a];
                pos = a;
            }
            list[pos] = x;
            return value;
        }
        public T Peek() { return list[0]; } // O(1)
        public void Clear() { list = new List<T>(); count = 0; } // O(1)
        public void TrimExcess() { list.TrimExcess(); } // O(1)
        public bool Contains(T item) { return list.Contains(item); } // O(n)
        void CopyTo(Array array, int index)
        {
            if (array == null)
                throw new ArgumentNullException();
            if (index < 0)
                throw new ArgumentOutOfRangeException();
            var tmp = new PriorityQueue<T>(comp, list.Count);
            for (var i = 0; i < count; i++) tmp.Enqueue(list[i]);
            while (!tmp.IsEmpty) array.SetValue(tmp.Dequeue(), index++);
        }
        bool ICollection.IsSynchronized { get { return false; } }
        object ICollection.SyncRoot { get { return this; } }
        public IEnumerator<T> GetEnumerator()
        {
            var tmp = new PriorityQueue<T>(comp, list.Count);
            for (var i = 0; i < count; i++) tmp.Enqueue(list[i]);
            while (!tmp.IsEmpty) yield return tmp.Dequeue();
        }
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        void ICollection.CopyTo(Array array, int index) { CopyTo(array, index); }
        int ICollection.Count { get { return count; } }
        public bool Any() { return count > 0; }
    }

    public class MyInputStream
    {
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(char separator = ' ')
        {
            this.separator = separator;
            inputStream = new Queue<string>();
        }

        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = Console.ReadLine().Split(separator);
            for (int i = 0; i < tmp.Length; ++i)
                inputStream.Enqueue(tmp[i]);
            return inputStream.Dequeue();
        }
        public string ReadLine() { return Console.ReadLine(); }
        public int ReadInt() { return int.Parse(Read()); }
        public long ReadLong() { return long.Parse(Read()); }
        public double ReadDouble() { return double.Parse(Read()); }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read(); return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt(); return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong(); return ret;}
    }
}

Submission Info

Submission Time
Task D - Transit Tree Path
User donguri411
Language C# (Mono 4.6.2.0)
Score 400
Code Size 9569 Byte
Status AC
Exec Time 1163 ms
Memory 41428 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 29 ms 9428 KB
sample_02.txt AC 29 ms 9428 KB
sample_03.txt AC 29 ms 11476 KB
subtask_1_1.txt AC 29 ms 9428 KB
subtask_1_10.txt AC 471 ms 18372 KB
subtask_1_11.txt AC 33 ms 9428 KB
subtask_1_12.txt AC 67 ms 11604 KB
subtask_1_13.txt AC 167 ms 13776 KB
subtask_1_14.txt AC 30 ms 13524 KB
subtask_1_15.txt AC 45 ms 16368 KB
subtask_1_16.txt AC 1058 ms 30204 KB
subtask_1_17.txt AC 1046 ms 34288 KB
subtask_1_18.txt AC 1157 ms 30200 KB
subtask_1_19.txt AC 1057 ms 30200 KB
subtask_1_2.txt AC 33 ms 11444 KB
subtask_1_20.txt AC 905 ms 32084 KB
subtask_1_21.txt AC 901 ms 31960 KB
subtask_1_22.txt AC 896 ms 30036 KB
subtask_1_23.txt AC 926 ms 32072 KB
subtask_1_24.txt AC 1145 ms 34772 KB
subtask_1_25.txt AC 1143 ms 41428 KB
subtask_1_26.txt AC 1152 ms 36816 KB
subtask_1_27.txt AC 1163 ms 34772 KB
subtask_1_28.txt AC 893 ms 34140 KB
subtask_1_3.txt AC 659 ms 25768 KB
subtask_1_4.txt AC 30 ms 11476 KB
subtask_1_5.txt AC 615 ms 16700 KB
subtask_1_6.txt AC 124 ms 19092 KB
subtask_1_7.txt AC 529 ms 18496 KB
subtask_1_8.txt AC 30 ms 9428 KB
subtask_1_9.txt AC 516 ms 30776 KB