学步园

用DFS,BFS始终过不了，一直TLE，后来不得已上了priority_queue。

方法有点类似dijkstra，节点比较的时候先比dist，dist相同的时候选择money小的。这种方法有一个好处是可以在priority_queue.top.position==end的时候直接结束，纯BFS,DFS则需要等到队列为空才能确定最后的答案。

用一个数组dist_s[i][j]=k记录状态，表示当达到第i个城市并消耗j元的时候，最短路径为k。记录状态的目的是剪枝，当往下搜索时碰到i,j相等，k却更大的路径，就可以忽略掉而不加到优先队列中。

#include <iostream><br /> #include <queue><br /> using namespace std;<br /> const int max_city=102;<br /> const int max_road=10002;<br /> struct Node<br /> {<br /> int position,dist,money;<br /> void Add(int a,int b,int c);<br /> };<br /> bool operator>(const Node& a,const Node& b)<br /> {<br /> if(a.dist==b.dist) return a.money>b.money;<br /> else return a.dist>b.dist;<br /> }<br /> priority_queue<Node,vector<Node>,greater<vector<Node>::value_type>> info;<br /> int min_dist=INT_MAX;<br /> int K,N,R;<br /> struct<br /> {<br /> int source,dest,lenght,cost;<br /> int next;<br /> }edge[max_road];<br /> int p[max_city];<br /> void Node::Add(int a,int b,int c)<br /> {<br /> position=a,dist=b,money=c;<br /> }<br /> int dist_s[max_city][10005];<br /> void exDijkstra(int start,int end)<br /> {<br /> memset(dist_s,-1,sizeof(dist_s));<br /> Node now,temp;<br /> now.dist=0;<br /> now.money=0;<br /> now.position=1;<br /> info.push(now);<br /> dist_s[1][0]=0;<br /> while(!info.empty())<br /> {<br /> now=info.top();<br /> info.pop();<br /> if(now.position==end)<br /> {<br /> min_dist=now.dist;<br /> return;<br /> }<br /> int t=p[now.position];<br /> while(t!=-1)<br /> {<br /> temp.dist=now.dist+edge[t].lenght;<br /> temp.money=now.money+edge[t].cost;<br /> temp.position=edge[t].dest;<br /> if(temp.money<=K)<br /> {<br /> if(temp.dist<dist_s[edge[t].dest][temp.money]||dist_s[edge[t].dest][temp.money]==-1)<br /> {<br /> dist_s[edge[t].dest][temp.money]=temp.dist;<br /> info.push(temp);<br /> }<br /> }<br /> t=edge[t].next;<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> scanf("%d%d%d",&K,&N,&R);<br /> memset(p,-1,sizeof(p));<br /> for(int i=0;i<R;i++)<br /> {<br /> scanf("%d%d%d%d",&edge[i].source,&edge[i].dest,&edge[i].lenght,&edge[i].cost);<br /> edge[i].next=p[edge[i].source];<br /> p[edge[i].source]=i;<br /> }<br /> exDijkstra(1,N);<br /> if(min_dist!=INT_MAX) printf("%d/n",min_dist);<br /> else printf("-1/n");<br /> return 0;<br /> }