Примерно решение №3

using System;
using System.Collections.Generic;
using System.Linq;
using Wintellect.PowerCollections;

namespace EmergencyPlan
{
    class Edge
    {
        public Edge(int first, int second, int time)
        {
            this.first = first;
            this.second = second;
            this.time = time;
        }
        public int first { set; get; }
        public int second { set; get; }
        public int time { set; get; }
    }

    class Program
    {
        private static List<Edge>[] graph;
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            var excapeRooms = Console.ReadLine()
                .Split()
                .Select(int.Parse)
                .ToList();

            int e = int.Parse(Console.ReadLine());
            graph = readGraph(n, e);

            int maxT = extractTime(Console.ReadLine());

            int[] timesToEscape = new int[n];
            for (int i = 0; i < timesToEscape.Length; i++)
            {
                timesToEscape[i] = int.MaxValue;
            }

            for (int i = 0; i < excapeRooms.Count; i++)
            {
                int exit = excapeRooms[i];
                int[] currentTimes = calculateAllTimes(exit, excapeRooms);

                for (int t = 0; t < currentTimes.Length; t++)
                {
                    if (currentTimes[t] < timesToEscape[t])
                    {
                        timesToEscape[t] = currentTimes[t];
                    }
                }
            }

            prepareOutput(timesToEscape, maxT);
        }

        private static int[] calculateAllTimes(int exit, List<int> exits)
        {
            int[] times = new int[graph.Length];
            for (int i = 0; i < times.Length; i++)
            {
                times[i] = int.MaxValue;
            }

            for (int room = 0; room < graph.Length; room++)
            {
                if (exits.Contains(room))
                {
                    times[room] = -1;
                    continue;
                }

                times[room] = calculateTime(room, exit);
                ;
            }

            return times;
        }

        private static int calculateTime(int start, int end)
        {
            int[] times = new int[graph.Length];
            for (int i = 0; i < times.Length; i++)
            {
                times[i] = int.MaxValue;
            }

            OrderedBag<int> queue = new OrderedBag<int>(
                Comparer<int>.Create((f, s) => times[f] - times[s]));

            times[start] = 0;
            queue.Add(start);

            while (queue.Count > 0)
            {
                int current = queue.RemoveFirst();

                if (current == end)
                {
                    break;
                }

                foreach (Edge edge in graph[current])
                {
                    int otherNode = edge.first == current ? edge.second : edge.first;
                    if (times[otherNode] == int.MaxValue)
                    {
                        queue.Add(otherNode);
                    }

                    int newTime = times[current] + edge.time;
                    if (newTime < times[otherNode])
                    {
                        times[otherNode] = newTime;
                        queue = new OrderedBag<int>(queue,
                            Comparer<int>.Create((f, s) => times[f] - times[s]));
                    }
                }
            }

            return times[end];
        }

        private static List<Edge>[] readGraph(int n, int e)
        {
            List<Edge>[] result = new List<Edge>[n];
            for (int i = 0; i < n; i++)
            {
                result[i] = new List<Edge>();
            }

            for (int i = 0; i < e; i++)
            {
                string[] data = Console.ReadLine()
                    .Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries)
                    .ToArray();

                int room1 = int.Parse(data[0]);
                int room2 = int.Parse(data[1]);
                int time = extractTime(data[2]);

                Edge edge = new Edge(room1, room2, time);
                result[room1].Add(edge);
                result[room2].Add(edge);
            }

            return result;
        }

        private static string convertTime(int time)
        {
            int hour = time / 3600;
            time -= (hour * 3600);

            int min = time / 60;
            time -= (min * 60);

            int sec = time;

            string h = String.Format("{0:0#}", hour);
            string m = String.Format("{0:0#}", min);
            string s = String.Format("{0:0#}", sec);
            return h + ":" + m + ":" + s;
        }

        private static int extractTime(string timeString)
        {
            int[] data = timeString
                .Split(new[] { ":" }, StringSplitOptions.RemoveEmptyEntries)
                .Select(int.Parse)
                .ToArray();
            // Time is calculated in seconds
            return data[0] * 60 + data[1];
        }

        private static void prepareOutput(int[] timesToEscape, int maxT)
        {
            for (int room = 0; room < timesToEscape.Length; room++)
            {
                int time = timesToEscape[room];

                if (time == -1)
                {
                    continue;
                }

                if (time == int.MaxValue)
                {
                    Console.WriteLine($"Unreachable {room} (N/A)");
                    continue;
                }

                if (time <= maxT)
                {
                    Console.WriteLine($"Safe {room} ({convertTime(time)})");
                }
                else
                {
                    Console.WriteLine($"Unsafe {room} ({convertTime(time)})");
                }
            }
        }
    }
}