开两个数组，lef，opt
lef[i]表示到点i最多剩下的钱
opt[i]表示到点i的最短距离
t表示bfs队列首的点,tmp为t的邻接点的指针
if(t.len + tmp->len > opt[n])  //中间点的距离超过目标点n的
    continue;
if (t.len + tmp->len > opt[tmp->to] && t.left - tmp->cost < lef[tmp->to])
//距离比邻接点大，且费的钱多
    continue;

if (tmp->cost <= t.left) { //还有钱走一条
    if(t.len + tmp->len <= opt[tmp->to]) { //选的路能改善此点的距离
		opt[tmp->to] = min(opt[tmp->to],t.len + tmp->len);
		lef[tmp->to] = max(lef[tmp->to],t.left - tmp->cost);
		ins.nw = tmp->to;
		ins.len = t.len + tmp->len;
		ins.left = t.left - tmp->cost;
		que.push(ins);
   } else if(t.left - tmp->cost >= lef[tmp->to]) {//选的路能改善到达此点的耗费
		opt[tmp->to] = min(opt[tmp->to],t.len + tmp->len);
		lef[tmp->to] = max(lef[tmp->to],t.left - tmp->cost);
		lef[tmp->to] = t.left - tmp->cost;
		ins.nw = tmp->to;
		ins.len = t.len + tmp->len;
		ins.left = t.left - tmp->cost;
		que.push(ins);
   }
}

• Re:话说我用 bfs+几个优化就过了,32ms 还可以 (114) xjtudaniel 2009-09-21 15:04:25
• Re:话说我用 bfs+几个优化就过了,32ms 还可以 (993) i_mist 2013-05-31 09:36:56