Namaran

Code daily. Without assist.

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. 直したあとの都市1はキューに2回入ります。末尾に残った古いほうを取り出したときは、どの都市の費用も下がらないので、何も起きずに次へ進みます。1つの都市が入るのは多くても2回で、dq の16個で足ります。