2026-09-01
tolls.c
#include <stdio.h>
static const int roads[][3] = {{0, 1, 1}, {0, 2, 0}, {2, 1, 0}, {1, 3, 1}};
int main(void) {
int dist[4] = {0, -1, -1, -1}, dq[16], head = 8, tail = 8;
dq[tail++] = 0;
while (head < tail) {
int v = dq[head++];
for (int i = 0; i < 4; i++) {
int from = roads[i][0], to = roads[i][1], toll = roads[i][2];
if (from == v && dist[to] == -1) {
dist[to] = dist[v] + toll;
dq[toll == 0 ? --head : tail++] = to;
}
}
}
printf("%d\n", dist[3]);
}
都市0から都市3まで、通る有料道路の本数の最小値を求めるつもりのコードです。道は roads の4本で、各行は {出発する都市, 着く都市, 通行料} の一方通行の道を表し、通行料1が有料道路、0が無料の道です。いまの出力は 2 で、本来の出力は 1 です。
Answer
Wrong
if (from == v && dist[to] == -1) {
dist[to] = dist[v] + toll;
dq[toll == 0 ? --head : tail++] = to;
}
都市0を取り出すと、roads の順に、都市1が有料の道で見つかって dist[1] = 1 で末尾に、都市2が無料の道で見つかって dist[2] = 0 で先頭に入ります。次に取り出す都市2からは、無料の道 {2, 1, 0} で都市1へ費用0で行けます。ところが dist[1] はもう -1 ではないので、条件が偽になって更新されません。都市1の費用は1のまま残り、都市3は 1 + 1 = 2 になります。
Right
if (from == v && (dist[to] == -1 || dist[v] + toll < dist[to])) {
dist[to] = dist[v] + toll;
dq[toll == 0 ? --head : tail++] = to;
}
すでに見つけた都市でも、今の道のほうが安ければ費用を書き換え、キューに入れ直します。都市1は費用0に下がって先頭に入り直し、そこから都市3は 0 + 1 = 1 になります。費用がすべて1の幅優先探索なら、先に見つけた都市ほど近いので、見つけた時点で費用が決まります。無料の道があると、あとから見つかった道のほうが安いことがあり、その性質は成り立ちません1。
- 直したあとの都市1はキューに2回入ります。末尾に残った古いほうを取り出したときは、どの都市の費用も下がらないので、何も起きずに次へ進みます。1つの都市が入るのは多くても2回で、
dqの16個で足ります。