学步园

题目链接：http://poj.org/problem?id=3259

题意：某农场主有多个农场，这些农场间的路径上有一些神奇的虫洞，能让农场主从一个农场到另一个农场并且时间会回溯一段，另外有一些正常的路径，需要花费农场主一定的时间从一个农场到另一个农场，注意虫洞是单向的．问是否有路径能使农场主从一点出发，并且回到该点的时间在他出发之前．

很有意思的一道题，不过做起来并不难，就是找出图中有无负环，用Bellman-Ford可以解决，这里采用的是SPFA:

普通queue版：

void SPFA(int from)<br /> {<br /> Edge *tmp;<br /> int u,v;<br /> while(!q.empty())q.pop();<br /> dis[from]=0;<br /> inq[from]=false;<br /> inn[from]++;<br /> q.push(from);</p> <p> while(!q.empty()){<br /> u=q.front();q.pop();<br /> inq[u]=false;<br /> if(inn[u]>=n){<br /> flag=true;<br /> return;<br /> }<br /> for(tmp=head[u];tmp;tmp=tmp->next){<br /> v=tmp->v;<br /> if(dis[v]==-1||dis[v]-dis[u]>tmp->t){<br /> dis[v]=dis[u]+tmp->t;<br /> if(!inq[v]){<br /> inq[v]=true;<br /> inn[v]++;<br /> q.push(v);<br /> }<br /> }<br /> }<br /> }</p> <p>}<br />  

priority_queue版：

void SPFA(int from)<br /> {<br /> Edge *tmp;<br /> int u,v;<br /> Q cur;<br /> while(!q.empty())q.pop();<br /> dis[from]=0;<br /> inq[from]=false;<br /> inn[from]++;<br /> q.push(Q(from,0));</p> <p> while(!q.empty()){<br /> cur=q.top();q.pop();<br /> u=cur.v;<br /> inq[u]=false;<br /> if(inn[u]>=n){<br /> flag=true;<br /> return;<br /> }<br /> for(tmp=head[u];tmp;tmp=tmp->next){<br /> v=tmp->v;<br /> if(dis[v]==-1||dis[v]-dis[u]>tmp->t){<br /> dis[v]=dis[u]+tmp->t;<br /> if(!inq[v]){<br /> inq[v]=true;<br /> inn[v]++;<br /> q.push(Q(v,dis[v]));<br /> }<br /> }<br /> }<br /> }</p> <p>}<br />