ダイクストラ 復元 注意点 prev 

struct Node{
  ll distance;
  ll index;
  ll prev=-1;
};

// ダイクストラアルゴリズム内部
{ // 省略
        while(!que.empty()){
            // 1番distanceが小さいノード
            Node n = que.top();que.pop();
 
            if(done[n.index])continue;
            
            // 確定
            done[n.index] = true;
            d[n.index] = n.distance;
            prev[n.index] = n.prev; // ここでprevを上書きすべき★1
 
            auto edge_list = graph[n.index];
            for(auto edge : edge_list){   
                // 短くなるノードがあれば
                if(!done[edge.to] && n.distance + edge.cost < d[edge.to]){
                    ll shorter_distance = n.distance + edge.cost;
                    que.push(Node(shorter_distance, edge.to, n.index));
                    // prev[edge.to] = n.index; // ここに書いてもバグります★2
                }
            }
        }
}
  • 具体的には★1の箇所でprevに入力しなければならなかった
  • 最初、★2のところでprevを書き換えたがそれはミス。edge.toの距離が3のものをpush, edge.toの距離が4のものをpush, とした場合、距離4の方でprevが上書きされてしまうため

追記：2024/01/06

  • 距離の更新をどこでやるかにもよる
    • que.pop()した直後で確定させるなら、★1でprevを書き換えるべき
    • for内でdも更新していくなら、★2でprevを書き換えても構わない。というか、こちらの形式(for内でd更新)の人が多いことを知った