Dijkstraの定数倍
dijkstra(){ distをINFで初期化 usedをfalseで初期化 優先順位つきキューに[0,始点]を突っ込む while(キューが空になるまで){ キューの先頭を取り出す dに距離を代入 vに頂点を代入 if(used[v] == true) continue used[v] = true dist[v] = d for(vから出る辺eを全部){ if(辺の容量が正) キューに[d+e.cost, e.to]を突っ込む } } }
みたいに書くと正しく動きますが、以下のような枝狩りのようなものがあるかないかによって10倍近くの定数倍の差が出ることがあるようです。
dijkstra(){ distをINFで初期化 dist[始点]は0 usedをfalseで初期化 優先順位つきキューに[0, 始点]を突っ込む while(キューが空になるまで){ キューの先頭を取り出す dに距離を代入 vに頂点を代入 if(used[v] == true) continue used[v] = true for(vから出る辺eを全部){ if(辺の容量が正 && d+e.cost < dist[e.to]){ dist[e.to] = d+e.cost キューに[d+e.cost, e.to]を突っ込む } } } }
これのせいで昨日のCFのEがTLEして悲しかった。
こんなに差が出る物なんですね・・・