关于dijkstra中的visit[]数组
  • 板块学术版
  • 楼主寒雨连夏
  • 当前回复19
  • 已保存回复19
  • 发布时间2021/8/13 21:58
  • 上次更新2023/11/4 10:45:39
查看原帖
关于dijkstra中的visit[]数组
58110
寒雨连夏楼主2021/8/13 21:58

在学校OJ上做一道题,删去visit数组后通过,加上visit数组后只有60,不知道大家有没有遇到过这种情况抑或是我的代码有什么问题?

void dij(int n,int s){
	priority_queue< pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > q;
	memset(ans,0x7f,sizeof(ans));
	memset(visit,0,sizeof(visit));
	q.push(make_pair(0,s));
	ans[s]=0;
	while(!q.empty()){
        int node=q.top().second;
        q.pop();
        for(int j=1;j<=n;j++){
	if(lt[node][j]){
	  if(ans[node]+lt[node][j]<ans[j])//若加上!visit[j]会爆40
    {
	    ans[j]=ans[node]+lt[node][j];
	  q.push(make_pair(lt[node][j],j));
	    		}
	    	}
	    }			
	}
}
2021/8/13 21:58
加载中...