有限制的单源最短路。

题目大意：给定一个图，图中的每条边有一个长度和一个费用，给出最大费用，求在不超过最大费用的前提下的最短路（从s到e）。

我的解法是BFS+优先队列，我们可以把<d,t,i>看成状态，i为结点编号，d为结点到源点的距离，t为目前剩余的费用，每次BFS时都选取d最小的状态进行扩展，直到到达目标结点。一开始，我还担心内存会爆掉，但是一下也没想到其他方法，就照这个想法写了，结果居然AC了。

由于要用到优先队列，所以只好临时学了一点STL，第一次提交是忘改用c++提交，CE了一次。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define N 101 5 #define M 10001 6  7 using namespace std; 8 typedef pair
         
          
           ,int> node; 9 priority_queue
           
            
             ,greater
             
               > pq;10 11 int n,m;12 int u[M],v[M],d[M],t[M],next[M];13 int first[N];14 15 int main()16 {17 int i,j,k,e,di,ti,ans;18 node tmp;19 while(~scanf("%d%d%d",&k,&n,&m))20 {21 for(e=1;e<=m;e++)22 {23 scanf("%d%d%d%d",&u[e],&v[e],&d[e],&t[e]);24 next[e]=first[u[e]];25 first[u[e]]=e;26 }27 pq.push(make_pair(make_pair(0,k),1));28 ans=-1;29 while(!pq.empty())30 {31 tmp=pq.top(),pq.pop();32 if(ans!=-1) continue;33 i=tmp.second;34 di=tmp.first.first;35 ti=tmp.first.second;36 if(i==n) ans=di;37 for(e=first[i];e;e=next[e])38 {39 j=v[e];40 if(ti>=t[e]) pq.push(make_pair(make_pair(di+d[e],ti-t[e]),j));41 }42 }43 printf("%d\n",ans);44 memset(first,0,sizeof(first));45 }46 return 0;47 }