AtCoder が提供しているABC（AtCoder Beginner Contest）325 のE問題をC++とPythonで解いてみました。ABC325は、2023年10月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Our clients, please wait a moment（Difficulty : 1093）
問題はリンク先をご覧ください。
ABC325 E問題 Our clients, please wait a moment
2種類の重みで最短距離を計算して、合わせて解を求めます。AtCoder Problems による Difficulty は、1093 でした。
解答案
グラフの頂点の最短距離を求める問題です。アルゴリズムは、Dijkstra法を使います。基本的な考え方は、重みが小さい辺から処理をすることにあります。このアルゴリズムのこれ以上の詳細は、この記事では省略します。
この問題は、社用車を使う場合と電車を使う場合で辺の重みが異なります。社用車→電車に切り替えることができます。逆はできません。
最初の都市（問題では都市1、プログラムでは都市0）から各都市の距離は、社用車を使った重みで計算します。最後の都市（問題では都市N、プログラムでは都市N-1）から各都市の距離は、電車を使った重みで計算します。
最後にどの都市で乗り換えるか全探索して、最小値を求めます。
C++ プログラム例（ABC325E）
プログラムは、いくつかの処理に分けて考えることができます。
- 重み付きグラフの定番コードと必要なマクロ定義（6ー13行目）
- 問題の入力をグラフとして変数 G に追加します（21ー30行目）。
- 都市0からの距離 dist1 をDijekstra法で求めます（32ー49行目）。重みが小さい辺から処理するために priority_queue を使いました。
- 都市N-1からの距離 distN をDijekstra法で求めます（51ー67行目）。計算方法は、都市0からの距離を求める場合と同じです。
- dist1 と distN の和の最小値を求めます（69ー72行目）。
以下が、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;
ll a, b, c;
cin >> n >> a >> b >> c;
vector<vector<Edge>> G(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ll d;
cin >> d;
if (i != j) {
G[i].push_back(Edge(j, d));
}
}
}
priority_queue<P, vector<P>, greater<P>> que;
vector<ll> dist1(n, INF);;
dist1[0] = 0;
que.push(P(0, 0));
while (!que.empty()) {
P p = que.top();
que.pop();
int now = p.second;
if (dist1[now] < p.first) {
continue;
}
for (auto next_v : G[now]) {
if (dist1[next_v.to] > dist1[now] + next_v.weight * a) {
dist1[next_v.to] = dist1[now] + next_v.weight * a;
que.push(P(dist1[next_v.to], next_v.to));
}
}
}
vector<ll> distN(n, INF);;
distN[n - 1] = 0;
que.push(P(0, n - 1));
while (!que.empty()) {
P p = que.top();
que.pop();
int now = p.second;
if (distN[now] < p.first) {
continue;
}
for (auto next_v : G[now]) {
if (distN[next_v.to] > distN[now] + next_v.weight * b + c) {
distN[next_v.to] = distN[now] + next_v.weight * b + c;
que.push(P(distN[next_v.to], next_v.to));
}
}
}
ll result = INF;
for (int i = 0; i < n; ++i) {
result = min(result, dist1[i] + distN[i]);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC325E）
基本的な考え方は、C++ と同じです。優先度付きキューとして heapq を使います。以下となります。
"""AtCoder Beginner Contest 325 E"""
import heapq
INF = 1 << 60
n, a, b, c = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n):
d = list(map(int, input().split()))
for j in range(n):
if i != j:
G[i].append((j, d[j]))
que = []
heapq.heapify(que)
dist1 = [INF] * n
dist1[0] = 0
heapq.heappush(que, (0, 0))
while que:
p = heapq.heappop(que)
now = p[1]
if dist1[now] < p[0]:
continue
for next_v in G[now]:
if dist1[next_v[0]] > dist1[now] + next_v[1] * a:
dist1[next_v[0]] = dist1[now] + next_v[1] * a
heapq.heappush(que, (dist1[next_v[0]], next_v[0]))
distN = [INF] * n
distN[n - 1] = 0
heapq.heappush(que, (0, n - 1))
while que:
p = heapq.heappop(que)
now = p[1]
if distN[now] < p[0]:
continue
for next_v in G[now]:
if distN[next_v[0]] > distN[now] + next_v[1] * b + c:
distN[next_v[0]] = distN[now] + next_v[1] * b + c
heapq.heappush(que, (distN[next_v[0]], next_v[0]))
print(min([dist1[i] + distN[i] for i in range(n)]))こちらも「AC」と判定されました。
最後に
グラフの頂点間の最短距離を求める問題は定番の問題です。この問題は、重みが2種類あり、組み合わせて最短距離を求めました。
引き続き ABC の問題を紹介していきます。
