AtCoder が提供しているABC（AtCoder Beginner Contest）342 のE問題をC++で解いてみました。ABC342は、2024年2月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Last Train（Difficulty : 1476）
問題はリンク先をご覧ください。
目的の駅に移動できるもっとも遅い電車をダイクストラ法で求めます。AtCoder Problems による Difficulty は 1476 でした。
解答案
ダイクストラ法は、典型アルゴリズム問題集のD問題で解説しています。今回は、駅 $N$ にたどり着く最終電車の時刻を同じ考え方で求めます。
C++ プログラム例（ABC342E）
配列 dist に駅 $N$ たどり着く最終時刻を格納します。ダイクストラ法は、距離が短い方から処理をしますが、この場合は、最終時刻が遅い駅から処理をします。
- グラフは、B から A の方向のみ辺を設定します（26行目）。
- 大きい値から取り出せるように優先度付きキュー que を用意します（30行目）。
- キューで取り出した駅から辺をたどり次の駅を処理します（40ー51行目）。
- 最初の電車を使ってもたどり着けない場合は、次の駅を処理します（41行目）。
- たどり着ける最終電車の時刻 next_start を求めます。
- next_start の方が遅い場合に、dist を更新して、キューに格納します。
以下が、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 L;
ll d;
ll k;
ll c;
Edge() { }
Edge(int t, ll tL, ll td, ll tk, ll tc) : to(t), L(tL), d(td), k(tk), c(tc) { }
};
int main()
{
int n, m;
cin >> n >> m;
vector<vector<Edge>> G(n + 1);
for (int i = 0; i < m; ++i) {
int a, b;
ll L, d, k, c;
cin >> L >> d >> k >> c >> a >> b;
G[b].push_back(Edge(a, L, d, k, c));
}
vector<ll> dist(n + 1, -1);
priority_queue<P> que;
dist[n] = INF;
que.push(P(INF, n));
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 (next_v.L + next_v.c > dist[now]) {
continue;
}
ll temp_k = ((dist[now] - next_v.c - next_v.L) / next_v.d) + 1;;
temp_k = min(temp_k, next_v.k);
ll next_start = next_v.L + (temp_k - 1) * next_v.d;;
if (next_start > dist[next_v.to]) {
dist[next_v.to] = next_start;
que.push(P(dist[next_v.to], next_v.to));
}
}
}
for (int i = 1; i < n; ++i) {
if (dist[i] == -1) {
cout << "Unreachable" << endl;
} else {
cout << dist[i] << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python プログラムの紹介を省略します。
最後に
解けなかった水Diffの問題を解説を見ながら解いています。
引き続き ABC の問題を紹介していきます。
