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して悲しかった。
こんなに差が出る物なんですね・・・
