최적화된 dijkstra 쌓기

1376 단어 그림 1.
작은 뿌리 더미를 이용하여 디스 그룹의 가장 짧은 거리를 찾을 때마다 복잡도를 최적화한다
작은 뿌리 더미만 보면 이 코드는 어렵지 않지만 세부 사항은 처리해야 한다
나는 손으로 쓴 더미지만, priority로queue가 더 쉬워요.
#include
using namespace std;
const int maxn=1000;
int f[maxn][maxn];
int vis[maxn];
int d[maxn];
const int inf=999999;
int len;
struct dot{
	int xu;
	int va;
}dis[maxn];//     ,          
//    push   
void push(dot n){ 
	dis[++len]=n;
	int son=len;
	while(son/2){
		if(dis[son/2].va>dis[son].va){
			swap(dis[son/2],dis[son]);
		    son/=2;
		}
		else break;
	}
}
//pop   
dot pop(){
	dot tp=dis[1];
	swap(dis[1],dis[len--]);
	int pa=1,son=2;
	while(son<=len){
		if(dis[son].va>dis[son+1].va&&sondis[pa].va)
		   break;
		 swap(dis[son],dis[pa]);
		 pa=son;
		 son=pa*2;
	}
	return tp;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		f[x][y]=f[y][x]=z;
	}
	fill(d,d+maxn,inf);
	push({1,0});
	d[1]=0;
	while(len){
		dot tp=pop();
		if(vis[tp.xu])//               ,
		//               ,          ,        ,
		//             
		 continue;
		vis[tp.xu]=1;
		for(int i=1;i<=n;i++){
		   if(f[tp.xu][i]&&!vis[i]&&d[i]>f[tp.xu][i]+tp.va)
		   {
		   	push({i,f[tp.xu][i]+tp.va});
		   	d[i]=f[tp.xu][i]+tp.va;//d        
		   }
		}
	}
	cout<

좋은 웹페이지 즐겨찾기