結果

問題 No.1382 Travel in Mitaru city
ユーザー さかぽんさかぽん
提出日時 2021-02-17 11:30:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 392 ms / 2,000 ms
コード長 8,409 bytes
コンパイル時間 3,826 ms
コンパイル使用メモリ 111,616 KB
実行使用メモリ 45,436 KB
最終ジャッジ日時 2024-09-13 22:39:28
合計ジャッジ時間 20,648 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
18,048 KB
testcase_01 AC 30 ms
18,048 KB
testcase_02 AC 30 ms
17,920 KB
testcase_03 AC 31 ms
18,048 KB
testcase_04 AC 30 ms
17,792 KB
testcase_05 AC 30 ms
17,920 KB
testcase_06 AC 149 ms
26,496 KB
testcase_07 AC 123 ms
25,856 KB
testcase_08 AC 84 ms
23,808 KB
testcase_09 AC 154 ms
25,856 KB
testcase_10 AC 147 ms
26,752 KB
testcase_11 AC 240 ms
34,304 KB
testcase_12 AC 254 ms
35,576 KB
testcase_13 AC 269 ms
36,344 KB
testcase_14 AC 238 ms
35,584 KB
testcase_15 AC 239 ms
34,688 KB
testcase_16 AC 386 ms
45,304 KB
testcase_17 AC 392 ms
45,048 KB
testcase_18 AC 379 ms
44,924 KB
testcase_19 AC 376 ms
45,052 KB
testcase_20 AC 371 ms
45,312 KB
testcase_21 AC 375 ms
45,300 KB
testcase_22 AC 378 ms
45,056 KB
testcase_23 AC 392 ms
45,056 KB
testcase_24 AC 385 ms
44,928 KB
testcase_25 AC 382 ms
45,044 KB
testcase_26 AC 322 ms
44,916 KB
testcase_27 AC 326 ms
44,920 KB
testcase_28 AC 310 ms
45,180 KB
testcase_29 AC 304 ms
45,308 KB
testcase_30 AC 275 ms
45,436 KB
testcase_31 AC 220 ms
41,728 KB
testcase_32 AC 264 ms
45,428 KB
testcase_33 AC 249 ms
43,904 KB
testcase_34 AC 173 ms
35,968 KB
testcase_35 AC 125 ms
32,000 KB
testcase_36 AC 196 ms
41,844 KB
testcase_37 AC 60 ms
23,680 KB
testcase_38 AC 214 ms
43,896 KB
testcase_39 AC 77 ms
25,216 KB
testcase_40 AC 170 ms
38,004 KB
testcase_41 AC 180 ms
39,672 KB
testcase_42 AC 216 ms
44,404 KB
testcase_43 AC 195 ms
41,592 KB
testcase_44 AC 93 ms
26,496 KB
testcase_45 AC 175 ms
38,144 KB
testcase_46 AC 121 ms
29,056 KB
testcase_47 AC 364 ms
41,848 KB
testcase_48 AC 252 ms
37,888 KB
testcase_49 AC 384 ms
44,772 KB
testcase_50 AC 182 ms
33,920 KB
testcase_51 AC 217 ms
39,288 KB
testcase_52 AC 254 ms
41,588 KB
testcase_53 AC 80 ms
24,576 KB
testcase_54 AC 133 ms
31,360 KB
testcase_55 AC 241 ms
42,356 KB
testcase_56 AC 97 ms
26,240 KB
testcase_57 AC 173 ms
34,688 KB
testcase_58 AC 57 ms
23,424 KB
testcase_59 AC 96 ms
26,368 KB
testcase_60 AC 237 ms
41,848 KB
testcase_61 AC 36 ms
20,096 KB
testcase_62 AC 30 ms
18,048 KB
testcase_63 AC 68 ms
22,884 KB
testcase_64 AC 45 ms
21,584 KB
testcase_65 AC 31 ms
18,304 KB
testcase_66 AC 36 ms
19,584 KB
testcase_67 AC 37 ms
20,096 KB
testcase_68 AC 49 ms
22,900 KB
testcase_69 AC 36 ms
19,712 KB
testcase_70 AC 52 ms
22,488 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