AtCoder が提供しているABC（AtCoder Beginner Contest）277 のE問題をC++とPythonで解いてみました。ABC277は、2022年11月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Crystal Switches（Difficulty : 1183）
問題はリンク先をご覧ください。
スイッチの状態に依存する2倍の頂点を用意して最短距離を求めます。AtCoder Problems による Difficulty は、1183 でした。
解答案
グラフの頂点の最短距離を求める問題です。
スイッチによって通行可能と通行不能になる辺によって頂点が結ばれています。以下の工夫によって最短距離を求めます。
- 頂点1から頂点N、頂点N＋１から頂点N＋Nを用意する。スイッチの状態に依存しますが、頂点1と頂点N+1は同じ頂点です。
- ai = 1 の場合、頂点 ui と 頂点 vi を重み１で結ぶ。
- ai = 0 の場合、頂点 ui+N と 頂点 vi+N を重み１で結ぶ。
- スイッチがある頂点iと頂点i+Nを重み0で結ぶ。
- 頂点1と頂点Nの距離と頂点1と頂点N+Nとの距離で短い方が解答となります。
C++ プログラム例（ABC277E）
最短距離は、Dijkstra法で求めます。
- 上記で考察したように辺を設定します（19ー36行目）。
- Dijkstra法は、優先度付きキューを使い実現します（38ー55行目）。
- 頂点Nと頂点N＋Nまでの距離がどちらも初期値（INF）であれば、到達しないため-1を出力します。そうでなければ、距離が短い方が解答となります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
typedef pair<int, int> P;
struct Edge {
int to;
int weight;
Edge() { }
Edge(int t, int w) : to(t), weight(w) { }
};
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<Edge>> G(2 * n + 1);
for (int i = 0; i < m; ++i) {
int u, v, a;
cin >> u >> v >> a;
if (a == 1) {
G[u].push_back(Edge(v, 1));
G[v].push_back(Edge(u, 1));
} else {
G[u + n].push_back(Edge(v + n, 1));
G[v + n].push_back(Edge(u + n, 1));
}
}
for (int i = 0; i < k; ++i) {
int s;
cin >> s;
G[s].push_back(Edge(s + n, 0));
G[s + n].push_back(Edge(s, 0));
}
vector<int> dist(2 * n + 1, INF);
priority_queue<P, vector<P>, greater<P>> que;
dist[1] = 0;
que.push(P(0, 1));
while (!que.empty()) {
P p = que.top();
que.pop();
int now = p.second;
if (dist[now] < p.first) {
continue;
}
for (auto next_v : G[now]) {
if (dist[next_v.to] > dist[now] + next_v.weight) {
dist[next_v.to] = dist[now] + next_v.weight;
que.push(P(dist[next_v.to], next_v.to));
}
}
}
if ((dist[n] == INF)&&(dist[n + n] == INF)) {
cout << -1 << endl;
} else {
cout << min(dist[n], dist[n + n]) << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC277E）
基本的な考え方はC++と同じです。優先度付きキューは、heapq を使います。
"""AtCoder Beginner Contest 277 E"""
import heapq
INF = 1 << 60
n, m, k = map(int, input().split())
G = [[] for i in range(2 * n + 1)]
for i in range(m):
u, v, a = map(int, input().split())
if a == 1:
G[u].append((v, 1))
G[v].append((u, 1))
else:
G[u + n].append((v + n, 1))
G[v + n].append((u + n, 1))
s = list(map(int, input().split()))
for i in range(k):
G[s[i]].append((s[i] + n, 0))
G[s[i] + n].append((s[i], 0))
que = []
heapq.heapify(que)
dist = [INF] * (2 * n + 1)
dist[1] = 0
heapq.heappush(que, (0, 1))
while que:
p = heapq.heappop(que)
now = p[1]
if dist[now] < p[0]:
continue
for next_v in G[now]:
if dist[next_v[0]] > dist[now] + next_v[1]:
dist[next_v[0]] = dist[now] + next_v[1]
heapq.heappush(que, (dist[next_v[0]], next_v[0]))
if dist[n] == INF and dist[n + n] == INF:
print(-1)
else:
print(min(dist[n], dist[n + n]))こちらも「AC」と判定されました。
最後に
スイッチのON/OFFにより、頂点1と頂点N＋1を移動すると考えるのは、うまい工夫です。もし似た問題を同じ手法で解くことができれば、気分がよいと思います。
引き続き ABC の問題を紹介していきます。
