読者です 読者をやめる 読者になる 読者になる

Dijkstraの定数倍

programming

ダイクストラ

dijkstra(){
	distをINFで初期化 dist[始点]は0
	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して悲しかった。
こんなに差が出る物なんですね・・・