POJ 1724 有限制的最短路

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

题目大意：

　　给定一个图，边有边权和费用，要求在给定总费用下，求从st到ed的最短路。

分析：

　　开始考虑着dp，离散dp，后来发现这个很水，直接写了bfs+优先队列，居然1A;

　　Discuss里面iSea神说到逆着bfs用vector可以存边，我就是这样写的，可是我觉得本来就该逆着做，因为是求st到ed的最短路，那么理应以ed为出发点，不是吗？（这句话应该是不妥的，但是你这样做保证你ac此类题）;

　　类似dijkstra的贪心，先贪距离，再贪费用，体现在优先队列的优先级上，具体见代码，另外我觉得这题还是数据弱吧，我连标记都删除了（那是因为我此题不会剪枝），最好用Discuss里面提到的A*方法吧（我还没有实现）。

注意这题有重边，反正用我的写法就保证不会出错的就是了，另外应该也有环，不过数据弱，我这个代码不会tle或mle的，数据大可能要进行拓扑我直觉告诉我。

代码：

poj1724

 1 /*1724    Accepted    576K    32MS    C++    1580B    2012-06-26 20:18:20*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 using namespace std;
10 
11 #define mpair make_pair
12 #define pii pair<int,int>
13 #define MM(a,b) memset(a,b,sizeof(a));
14 typedef long long lld;
15 typedef unsigned long long u64;
16 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
17 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
18 #define maxn 110
19 
20 int n,m,K;
21 typedef pair< int, pii > pi;
22 vector< pi > e[maxn];
23 
24 struct Node{
25     int u, d, cost;
26     Node(int u_,int d_,int cost_){u=u_,d=d_,cost=cost_;}
27     bool operator<(Node a)const{
28         return d>a.d || ( d==a.d && cost>a.cost );
29     }
30 };
31 priority_queue<Node> Q;
32 
33 #define x first
34 #define y second
35 int bfs(int st,int ed){
36     while( !Q.empty() ) Q.pop();
37     Q.push( Node( st, 0, 0 ) );
38     while( !Q.empty() ){
39         Node a= Q.top(); Q.pop();
40         int u= a.u, d= a.d, cost= a.cost;
41         if( u==ed ) return d;
42         for(int i=0;i<e[u].size();++i){
43             int v= e[u][i].x, w= e[u][i].y.x, t= e[u][i].y.y;
44             if( cost+t > K ) continue;
45             Q.push( Node( v, d+w, cost+t ) );
46         }
47     }
48     return -1;
49 }
50 
51 int main()
52 {
53     //freopen("poj1724.in","r",stdin);
54     while( cin>>K>>n>>m ){
55         for(int i=1;i<=n;++i) e[i].clear();
56         while(m--){
57             int u,v,l,t;
58             scanf("%d%d%d%d", &u, &v, &l, &t);
59             e[v].push_back( mpair( u, pii(l,t) ) );
60         }
61         cout<< bfs(n,1) <<endl;
62     }
63 }

一毛原创作品，转载请注明出处。