为什么这题用SPFA这么快?
查看原帖
为什么这题用SPFA这么快?
86624
洛谷Onlinejudge楼主2020/9/1 00:36

我交了两次:

第一次(没用SPFA)

第二次(被迫装上SPFA)

其实唯一的差别就是:

第一次:

inline void DP(void){
	queue <int> Queue;
	Queue.push(Set[Start]);
	Val[Set[Start]]=Sum[Set[Start]];
	while(!Queue.empty()){
		int This=Queue.front();
		Queue.pop();
		if(S[This]==true)
			Max=max(Max,Val[This]);
		for(register int i=Head2[This];i;i=E2[i].Next){
			int To=E2[i].To;
			Val[To]=max(Val[To],Sum[To]+Val[This]);
			Queue.push(To);
		}
	}
	return;
}

第二次:

inline void DP(void){
	queue <int> Queue;
	Queue.push(Set[Start]);
	Visited[Set[Start]]=true;
	Val[Set[Start]]=Sum[Set[Start]];
	while(!Queue.empty()){
		int This=Queue.front();
		Queue.pop();
		Visited[This]=false;
		for(register int i=Head2[This];i;i=E2[i].Next){
			int To=E2[i].To;
			if(Val[To]<Val[This]+Sum[To]){
				Val[To]=Val[This]+Sum[To];
				if(Visited[To]==false){
					Visited[To]=true;
					Queue.push(To);
				}
			}
		}
	}
	for(register int i=1;i<=Root;i++)
		if(S[i]==true)
			Max=max(Max,Val[i]);
	return;
}

大佬可以帮忙解释一下吗?

2020/9/1 00:36
加载中...