AtCoder が提供しているABC（AtCoder Beginner Contest）362 D問題をC++とPythonで解いてみました。ABC362は、2024年7月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Shortest Path 3（Difficulty : 634）
問題の詳細は、リンク先をご覧ください。
重み付き辺のグラフの単一始点最短経路問題です。AtCoder Problems による Difficulty は 634 でした。
解答案
典型アルゴリズム問題集 D問題で「単一始点最短経路問題」を紹介しました。頂点の重みを辺の重みに加えれば、同じようにダイクストラ法（Dijkstra’s algorithm）が使えます。
C++ プログラム例（ABC362D）
辺を読み込むときに、$u_i \rightarrow v_i$ の辺に重み $a_{v_i} $ を加えます。同じように $v_i \rightarrow u_i$ の辺に重み $a_{u_i} $ を加えます（29、30行目）。この処理以外は、ダイクストラ法の定番コードです。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
typedef pair<ll, int> P;
struct Edge {
int to;
ll weight;
Edge() { }
Edge(int t, ll w) : to(t), weight(w) { }
};
int main()
{
int n, m;
cin >> n >> m;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<Edge>> G(n);
for (int i = 0; i < m; ++i) {
int u, v;
ll b;
cin >> u >> v >> b;
--u;
--v;
G[u].push_back(Edge(v, b + a[v]));
G[v].push_back(Edge(u, b + a[u]));
}
vector<ll> dist(n, INF);
priority_queue<P, vector<P>, greater<P>> que;
dist[0] = a[0];
que.push(P(0, 0));
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));
}
}
}
for (int i = 1; i < n; ++i) {
cout << dist[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC362D）
Python版も基本的な考え方は同じです。優先度付きキューは heapq を使いました。以下がプログラムです。
"""AtCoder Beginner Contest 362 D"""
import heapq
INF = 1 << 60
n, m = map(int, input().split())
a = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(m):
u, v, b = map(int, input().split())
u -= 1
v -= 1
G[u].append((v, b + a[v]))
G[v].append((u, b + a[u]))
que = []
heapq.heapify(que)
dist = [INF] * n
dist[0] = a[0]
heapq.heappush(que, (a[0], 0))
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]))
print(*dist[1:])こちらも「AC」と判定されました。
最後に
典型問題であったためか茶色 Diff でした。このような問題は速く解く必要があるようです。
引き続き ABC の問題を紹介していきます。
