結果

問題 No.1382 Travel in Mitaru city
ユーザー さかぽんさかぽん
提出日時 2021-02-17 11:30:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 420 ms / 2,000 ms
コード長 8,409 bytes
コンパイル時間 6,372 ms
コンパイル使用メモリ 112,060 KB
実行使用メモリ 51,708 KB
最終ジャッジ日時 2023-10-11 22:51:14
合計ジャッジ時間 28,866 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
20,644 KB
testcase_01 AC 64 ms
22,812 KB
testcase_02 AC 64 ms
22,744 KB
testcase_03 AC 65 ms
20,776 KB
testcase_04 AC 64 ms
20,704 KB
testcase_05 AC 64 ms
22,764 KB
testcase_06 AC 180 ms
27,060 KB
testcase_07 AC 158 ms
30,476 KB
testcase_08 AC 119 ms
28,376 KB
testcase_09 AC 186 ms
28,464 KB
testcase_10 AC 178 ms
27,316 KB
testcase_11 AC 280 ms
34,744 KB
testcase_12 AC 295 ms
38,248 KB
testcase_13 AC 304 ms
38,736 KB
testcase_14 AC 270 ms
38,032 KB
testcase_15 AC 274 ms
39,356 KB
testcase_16 AC 416 ms
51,708 KB
testcase_17 AC 399 ms
47,648 KB
testcase_18 AC 420 ms
49,780 KB
testcase_19 AC 414 ms
47,664 KB
testcase_20 AC 420 ms
49,664 KB
testcase_21 AC 420 ms
47,592 KB
testcase_22 AC 410 ms
47,600 KB
testcase_23 AC 413 ms
47,776 KB
testcase_24 AC 410 ms
47,680 KB
testcase_25 AC 410 ms
47,616 KB
testcase_26 AC 348 ms
47,664 KB
testcase_27 AC 350 ms
51,608 KB
testcase_28 AC 330 ms
47,616 KB
testcase_29 AC 335 ms
49,700 KB
testcase_30 AC 309 ms
49,684 KB
testcase_31 AC 261 ms
46,288 KB
testcase_32 AC 305 ms
49,904 KB
testcase_33 AC 287 ms
48,452 KB
testcase_34 AC 208 ms
40,332 KB
testcase_35 AC 162 ms
34,316 KB
testcase_36 AC 230 ms
46,676 KB
testcase_37 AC 94 ms
28,372 KB
testcase_38 AC 243 ms
46,556 KB
testcase_39 AC 111 ms
29,848 KB
testcase_40 AC 200 ms
42,444 KB
testcase_41 AC 212 ms
44,176 KB
testcase_42 AC 245 ms
48,924 KB
testcase_43 AC 224 ms
44,172 KB
testcase_44 AC 127 ms
31,148 KB
testcase_45 AC 205 ms
42,572 KB
testcase_46 AC 156 ms
31,544 KB
testcase_47 AC 389 ms
44,244 KB
testcase_48 AC 287 ms
40,280 KB
testcase_49 AC 417 ms
49,392 KB
testcase_50 AC 217 ms
36,468 KB
testcase_51 AC 251 ms
43,588 KB
testcase_52 AC 287 ms
46,216 KB
testcase_53 AC 111 ms
25,060 KB
testcase_54 AC 167 ms
35,988 KB
testcase_55 AC 281 ms
46,964 KB
testcase_56 AC 130 ms
30,864 KB
testcase_57 AC 204 ms
35,192 KB
testcase_58 AC 91 ms
27,728 KB
testcase_59 AC 128 ms
30,956 KB
testcase_60 AC 276 ms
44,368 KB
testcase_61 AC 70 ms
24,860 KB
testcase_62 AC 64 ms
22,880 KB
testcase_63 AC 101 ms
29,144 KB
testcase_64 AC 79 ms
22,880 KB
testcase_65 AC 66 ms
20,720 KB
testcase_66 AC 68 ms
20,804 KB
testcase_67 AC 70 ms
24,876 KB
testcase_68 AC 82 ms
27,156 KB
testcase_69 AC 67 ms
18,804 KB
testcase_70 AC 87 ms
26,980 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using Bang.Graphs.Int.Spp;

class C
{
	static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
	static (int, int, int, int) Read4() { var a = Read(); return (a[0], a[1], a[2], a[3]); }
	static void Main()
	{
		var (n, m, s, t) = Read4();
		var p = Read();
		var map = GraphConsole.ReadUnweightedMap(n + 1, m, false);

		int x = p[s - 1], y = 0;
		var u = new bool[n + 1];
		var q = PriorityQueue<int>.CreateWithKey(v => p[v - 1], true);
		u[s] = true;
		q.Push(s);

		while (q.Any)
		{
			var (v, pv) = q.Pop();
			if (x > pv)
			{
				x = pv;
				y++;
			}

			foreach (var nv in map[v])
			{
				if (u[nv]) continue;
				u[nv] = true;
				q.Push(nv);
			}
		}
		Console.WriteLine(y);
	}
}

namespace Bang.Graphs.Int.Spp
{
	public struct Edge
	{
		public static Edge Invalid { get; } = new Edge(-1, -1, long.MinValue);

		public int From { get; }
		public int To { get; }
		public long Cost { get; }

		public Edge(int from, int to, long cost = 1) { From = from; To = to; Cost = cost; }
		public void Deconstruct(out int from, out int to) { from = From; to = To; }
		public void Deconstruct(out int from, out int to, out long cost) { from = From; to = To; cost = Cost; }
		public override string ToString() => $"{From} {To} {Cost}";

		public static implicit operator Edge(int[] e) => new Edge(e[0], e[1], e.Length > 2 ? e[2] : 1);
		public static implicit operator Edge(long[] e) => new Edge((int)e[0], (int)e[1], e.Length > 2 ? e[2] : 1);
		public static implicit operator Edge((int from, int to) v) => new Edge(v.from, v.to);
		public static implicit operator Edge((int from, int to, long cost) v) => new Edge(v.from, v.to, v.cost);

		public Edge Reverse() => new Edge(To, From, Cost);
	}

	public static class GraphConsole
	{
		static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

		public static Edge[] ReadEdges(int count)
		{
			return Array.ConvertAll(new bool[count], _ => (Edge)Read());
		}

		public static UnweightedMap ReadUnweightedMap(int vertexesCount, int edgesCount, bool directed)
		{
			return new UnweightedMap(vertexesCount, ReadEdges(edgesCount), directed);
		}
	}

	public static class GraphConvert
	{
		public static void UnweightedEdgesToMap(List<int>[] map, Edge[] edges, bool directed)
		{
			foreach (var e in edges)
			{
				map[e.From].Add(e.To);
				if (!directed) map[e.To].Add(e.From);
			}
		}

		public static void UnweightedEdgesToMap(List<int>[] map, int[][] edges, bool directed)
		{
			foreach (var e in edges)
			{
				map[e[0]].Add(e[1]);
				if (!directed) map[e[1]].Add(e[0]);
			}
		}

		public static void WeightedEdgesToMap(List<Edge>[] map, Edge[] edges, bool directed)
		{
			foreach (var e in edges)
			{
				map[e.From].Add(e);
				if (!directed) map[e.To].Add(e.Reverse());
			}
		}

		public static void WeightedEdgesToMap(List<Edge>[] map, int[][] edges, bool directed)
		{
			foreach (var e0 in edges)
			{
				Edge e = e0;
				map[e.From].Add(e);
				if (!directed) map[e.To].Add(e.Reverse());
			}
		}

		public static List<int>[] UnweightedEdgesToMap(int vertexesCount, Edge[] edges, bool directed)
		{
			var map = Array.ConvertAll(new bool[vertexesCount], _ => new List<int>());
			UnweightedEdgesToMap(map, edges, directed);
			return map;
		}

		public static List<int>[] UnweightedEdgesToMap(int vertexesCount, int[][] edges, bool directed)
		{
			var map = Array.ConvertAll(new bool[vertexesCount], _ => new List<int>());
			UnweightedEdgesToMap(map, edges, directed);
			return map;
		}

		public static List<Edge>[] WeightedEdgesToMap(int vertexesCount, Edge[] edges, bool directed)
		{
			var map = Array.ConvertAll(new bool[vertexesCount], _ => new List<Edge>());
			WeightedEdgesToMap(map, edges, directed);
			return map;
		}

		public static List<Edge>[] WeightedEdgesToMap(int vertexesCount, int[][] edges, bool directed)
		{
			var map = Array.ConvertAll(new bool[vertexesCount], _ => new List<Edge>());
			WeightedEdgesToMap(map, edges, directed);
			return map;
		}
	}

	public class UnweightedMap
	{
		public int VertexesCount { get; }
		List<int>[] map;
		public List<int>[] RawMap => map;
		public int[] this[int vertex] => map[vertex].ToArray();

		public UnweightedMap(int vertexesCount, List<int>[] map)
		{
			VertexesCount = vertexesCount;
			this.map = map;
		}

		public UnweightedMap(int vertexesCount)
		{
			VertexesCount = vertexesCount;
			map = Array.ConvertAll(new bool[vertexesCount], _ => new List<int>());
		}

		public UnweightedMap(int vertexesCount, Edge[] edges, bool directed) : this(vertexesCount)
		{
			AddEdges(edges, directed);
		}

		public UnweightedMap(int vertexesCount, int[][] edges, bool directed) : this(vertexesCount)
		{
			AddEdges(edges, directed);
		}

		public void AddEdges(Edge[] edges, bool directed)
		{
			GraphConvert.UnweightedEdgesToMap(map, edges, directed);
		}

		public void AddEdges(int[][] edges, bool directed)
		{
			GraphConvert.UnweightedEdgesToMap(map, edges, directed);
		}

		public void AddEdge(Edge edge, bool directed)
		{
			map[edge.From].Add(edge.To);
			if (!directed) map[edge.To].Add(edge.From);
		}

		public void AddEdge(int from, int to, bool directed)
		{
			map[from].Add(to);
			if (!directed) map[to].Add(from);
		}
	}

	/// <summary>
	/// 優先度付きキューを表します。
	/// </summary>
	/// <typeparam name="T">オブジェクトの型。</typeparam>
	/// <remarks>
	/// 二分ヒープによる実装です。<br/>
	/// 内部では 1-indexed のため、raw array を直接ソートする用途では使われません。
	/// </remarks>
	public class PriorityQueue<T>
	{
		public static PriorityQueue<T> Create(bool descending = false)
		{
			var c = Comparer<T>.Default;
			return descending ?
				new PriorityQueue<T>((x, y) => c.Compare(y, x)) :
				new PriorityQueue<T>(c.Compare);
		}

		public static PriorityQueue<T> Create<TKey>(Func<T, TKey> keySelector, bool descending = false)
		{
			if (keySelector == null) throw new ArgumentNullException(nameof(keySelector));

			var c = Comparer<TKey>.Default;
			return descending ?
				new PriorityQueue<T>((x, y) => c.Compare(keySelector(y), keySelector(x))) :
				new PriorityQueue<T>((x, y) => c.Compare(keySelector(x), keySelector(y)));
		}

		public static PriorityQueue<T, TKey> CreateWithKey<TKey>(Func<T, TKey> keySelector, bool descending = false)
		{
			var c = Comparer<TKey>.Default;
			return descending ?
				new PriorityQueue<T, TKey>(keySelector, (x, y) => c.Compare(y.key, x.key)) :
				new PriorityQueue<T, TKey>(keySelector, (x, y) => c.Compare(x.key, y.key));
		}

		List<T> l = new List<T> { default };
		Comparison<T> c;

		public T First
		{
			get
			{
				if (l.Count <= 1) throw new InvalidOperationException("The heap is empty.");
				return l[1];
			}
		}

		public int Count => l.Count - 1;
		public bool Any => l.Count > 1;

		internal PriorityQueue(Comparison<T> comparison)
		{
			c = comparison ?? throw new ArgumentNullException(nameof(comparison));
		}

		// x の親: x/2
		// x の子: 2x, 2x+1
		void UpHeap(int i)
		{
			for (int j; (j = i >> 1) > 0 && c(l[j], l[i]) > 0; i = j)
				(l[i], l[j]) = (l[j], l[i]);
		}

		void DownHeap(int i)
		{
			for (int j; (j = i << 1) < l.Count; i = j)
			{
				if (j + 1 < l.Count && c(l[j], l[j + 1]) > 0) j++;
				if (c(l[i], l[j]) > 0) (l[i], l[j]) = (l[j], l[i]); else break;
			}
		}

		public void Push(T value)
		{
			l.Add(value);
			UpHeap(l.Count - 1);
		}

		public void PushRange(IEnumerable<T> values)
		{
			if (values != null) foreach (var v in values) Push(v);
		}

		public T Pop()
		{
			if (l.Count <= 1) throw new InvalidOperationException("The heap is empty.");

			var r = l[1];
			l[1] = l[l.Count - 1];
			l.RemoveAt(l.Count - 1);
			DownHeap(1);
			return r;
		}
	}

	// キーをキャッシュすることにより、キーが不変であることを保証します。
	public class PriorityQueue<T, TKey> : PriorityQueue<(T value, TKey key)>
	{
		Func<T, TKey> KeySelector;

		internal PriorityQueue(Func<T, TKey> keySelector, Comparison<(T value, TKey key)> comparison) : base(comparison)
		{
			KeySelector = keySelector ?? throw new ArgumentNullException(nameof(keySelector));
		}

		public void Push(T value)
		{
			Push((value, KeySelector(value)));
		}

		public void PushRange(IEnumerable<T> values)
		{
			if (values != null) foreach (var v in values) Push(v);
		}
	}
}
0