http://poj.org/problem?id=1724
这道题我使用的是dijkstra,在处理进队列是条件是if(st2.c+c1<=k)，以这个条件来更新距离。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 #define maxn 20000 6 using namespace std; 7 const int inf=1<<30; 8 9 int head[maxn],e,k,n,r,s,d,l,t; 10 int dis[maxn]; 11 bool vis[maxn]; 12 int ans; 13 14 struct node 15 { 16 int u,v,w,c; 17 int next; 18 bool operator <(const node &a)const 19 { 20 return ((w>a.w)||(w>a.w&&c>a.c)); 21 } 22 } p[maxn]; 23 node st1,st2; 24 25 void add(int u,int v,int w,int c) 26 { 27 p[e].u=u; 28 p[e].v=v; 29 p[e].w=w; 30 p[e].c=c; 31 p[e].next=head[u]; 32 head[u]=e++; 33 } 34 35 void dijkstra() 36 { 37 memset(vis,false,sizeof(vis)); 38 priority_queue<node>q; 39 vis[1]=true; 40 st1.v=1; 41 st1.c=0; 42 st1.w=0; 43 q.push(st1); 44 while(!q.empty()) 45 { 46 st2=q.top(); 47 q.pop(); 48 int u=st2.v; 49 //printf("!!!%d ",dis[u]); 50 if(st2.v==n) 51 { 52 ans=st2.w; 53 return ; 54 } 55 for(int i=head[u]; i!=-1; i=p[i].next) 56 { 57 int w1=p[i].w; 58 int c1=p[i].c; 59 if(st2.c+c1<=k) 60 { 61 st1.v=p[i].v; 62 st1.c=st2.c+c1; 63 st1.w=st2.w+w1; 64 vis[p[i].v]=true; 65 q.push(st1); 66 } 67 } 68 } 69 } 70 int main() 71 { 72 while(scanf("%d",&k)!=EOF) 73 { 74 scanf("%d",&n); 75 scanf("%d",&r); 76 memset(head,-1,sizeof(head)); 77 e=0; 78 for(int i=0; i<r; i++) 79 { 80 scanf("%d%d%d%d",&s,&d,&l,&t); 81 add(s,d,l,t); 82 } 83 dijkstra(); 84 if(ans==inf) 85 { 86 printf("-1 "); 87 } 88 else printf("%d ",ans); 89 } 90 return 0; 91 }