double prime() {
	double cost = 0;
	double len = 0;
	int i,j;
	priority_queue<node> pq;
	memset(vis, 0, sizeof(vis));
	node now;
	now.s = 0;
	vis[0] = true;
	for(i=1;i<n;i++) {
		now.t = i;
		now.dis = abs(vi[0].z-vi[i].z) - rate*dist[0][i];
		pq.push(now);
	}
	while(!pq.empty()) {
		now = pq.top();
		pq.pop();
		if(vis[now.t]) continue;
		vis[now.t] = true;
		len += dist[now.s][now.t];
		cost += abs(vi[now.s].z-vi[now.t].z);
		node next;
		next.s = now.t;
		for(i=1;i<n;i++) {
			if(!vis[i]) {
				next.t = i;
				next.dis = abs(vi[next.s].z-vi[next.t].z) - rate*dist[next.s][next.t];
				pq.push(next);
			}
		}
	}
	return cost / len;
}

• 还有二分枚举g++会WA，C++会TLE，好郁闷啊>.<，迭代更高效吗？ (0) huangwei 2007-09-12 20:14:09