N 頂点 M 辺の単純無向グラフがあり、頂点 p[i] に体力は h[i] の警備員がいる。ひとり以上の警備員がたどり着ける頂点はどれか？すべて列挙せよというのが問題の趣旨です。
警備員の体力がすべて同じなら多始点の幅優先探索をして、距離が h 以内の頂点をすべて列挙すればいいのですが、この問題は警備員の体力がそれぞれ異なっています。さてどうすればよいのでしょうか？
ここではダイクストラ法の反転させたようなアルゴリズムを採用します。
Contents
ダイクストラ法とは？
ダイクストラ法は以下のような方法です。
頂点数と同じ長さの配列 D を用意し、n が開始地点であるときは D[n] = 0、それ以外の要素は ∞ で初期化する。
優先度付きキュー（ priority が小さいものが先に取り出される）に開始地点 s を格納する。このとき priority は 0 とする。
優先度付きキューから値をとりだす。この値を u とする。この段階で開始地点から u までの移動に必要な距離が D[u] であると確定する。
u から移動可能な頂点 v と移動に必要な距離 w(u, v) を調べる。
D[v] よりも D[u] + w(u, v) のほうが小さい場合は D[v] を D[u] + w(u, v) で更新して優先度付きキューに v を格納する。このとき priority は更新された D[v] とする。そうでないときは何もしない。
優先度付きキューが空になるまで上記を繰り返す。処理が終わったとき D[v] の値が s から v までの移動に必要な距離となっている。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// 枝で頂点 u と頂点 v がつながっていて距離は w である struct E { int u; int v; int w; } int[] D = new int[N]; bool[] confirmed = new bool[N]; // すでに D[u] の値は確定しているか？ for (int i = 0; i < N; i++) D[i] = int.MaxValue; PriorityQueue<int, int> q = new PriorityQueue<int, int>(); q.Enqueue(s, 0); D[s] = 0; while (q.Count > 0) { int u = q.Dequeue(); // この段階で D[u] の値は確定する if (confirmed[u]) continue; confirmed[u] = true; foreach (var e in E[u]) { int v = e.v; if (D[v] > D[u] + e.w) { D[v] = D[u] + e.w; q.Enqueue(v, D[v]); } } } // D[v]：s から v までの距離 |
変則的な多始点ダイクストラ法
この問題の場合は、体力は h[i] の警備員がたどり着ける頂点を知りたいので最初に警備員がいる頂点 v は D[v] = h[v]、それ以外の頂点はD[v] = h[v] で初期化しておきます。そして警備員が移動可能な頂点には体力を 1 減らした警備員のコピーを配置していきます。警備員をこれ以上コピーできなくなったら警備員がいる頂点を列挙すればこれが答えとなります。
まず指定された頂点から指定された距離内にある頂点を取得するためのクラスを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
class Solver { int N; // 頂点の数 List<Edge>[] Edges; // 辺 class Edge { public Edge(int v, int w) { V = v; W = w; } public int V = 0; public int W = 0; } public Solver(int n) { N = n; Edges = new List<Edge>[N]; for (int i = 0; i < N; i++) Edges[i] = new List<Edge>(); } /// <summary> /// 頂点 a から 頂点 b へ重み w を辺を追加する /// </summary> /// <param name="a"></param> /// <param name="b"></param> /// <param name="w"></param> public void AddEdge(int a, int b, int w) { Edges[a].Add(new Edge(b, w)); } /// <summary> /// 各頂点が S から 距離 D 内にあるか調べる /// </summary> /// <param name="S">警備員がいる頂点番号の配列</param> /// <param name="D">各警備員の体力</param> /// <returns></returns> public bool[] IsWithinDistance(int[] S, int[] D) { long[] canMoves = new long[N]; bool[] confirmed = new bool[N]; for (int i = 0; i < N; i++) canMoves[i] = -1; int len = S.Length; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); for (int i = 0; i < len; i++) { pq.Enqueue(S[i], -D[i]); // 移動可能量が大きい警備員を優先するので Priority の符号を反転する canMoves[S[i]] = D[i]; } while (pq.Count > 0) { int u = pq.Dequeue(); long canMove = canMoves[u]; if (confirmed[u]) continue; confirmed[u] = true; foreach (Edge e in Edges[u]) { int v = e.V; long newCanMove = canMove - e.W; if (canMoves[v] < newCanMove) { canMoves[v] = newCanMove; pq.Enqueue(v, -newCanMove); } } } bool[] rets = new bool[N]; for (int i = 0; i < N; i++) { if (canMoves[i] >= 0) rets[i] = true; } return rets; } } |
Solverクラスから解を求めます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class Program { static void Main() { int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] vs = ReadIntArray(); int N = vs[0]; int M = vs[1]; int K = vs[2]; Solver solver = new Solver(N); for (int i = 0; i < M; i++) { vs = ReadIntArray(); int a = vs[0] - 1; int b = vs[1] - 1; solver.AddEdge(a, b, 1); solver.AddEdge(b, a, 1); } int[] P = new int[K]; int[] H = new int[K]; for (int i = 0; i < K; i++) { vs = ReadIntArray(); P[i] = vs[0] - 1; H[i] = vs[1]; } bool[] rets = solver.IsWithinDistance(P, H); List<int> ans = new List<int>(); for (int i = 0; i < N; i++) { if(rets[i]) ans.Add(i + 1); } Console.WriteLine(ans.Count); Console.WriteLine(string.Join(" ", ans)); } } |
