pku 1724 ROADS BFS +优先队列

http://poj.org/problem?id=1724

题意：

Bob现在有的钱数为k，他想从城市1到城市n，给出m条连接两个城市的有向边，并且给出路的长度w，和经过这条路要交的钱数c。问Bob在花的过路费不超过k的前提下能到达城市n的最短路径为多长。

思路：

才开始我想spfa来做，开两个数组dis记录距离最短disw记录话费最小，在松弛的时候进行距离与费用的限制来进行，可是发现当某一个点被多个点更新时，比如i点被更新为[7,12] [9,9] [12,7]

 那我们选择哪一个呢？如果我们选择路径短的话，[7,12] 可是可能时间总和就会超出k,如果我们选择费用小的话[12,7] 可是路径的长度可能不如选择[9,9]的短，所以无法做出选择。

这里我们用bfs来做，队列用优先队列实现，这里有了两个保证：1：bfs本身搜索的过程就是找最值得过程，我们用它来实现费用最小；2：优先队列每次出来的是路径最小的那么我们又得到了路径最小的满足。一举两得啊！！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 107
using namespace std;

const int inf = 0x7fffffff;

struct node
{
    int v;
    int l,w;
    node *next;
}H[maxn*maxn],*head[maxn];

//搜索过程中的记录
struct nn
{
    int cost;
    int len;
    int pos;
    friend bool operator < (nn a, nn b)
    {
        return a.len > b.len;
    }
};

int n,m,k,t,ans;
priority_queue<nn>que;


void insert(int u,int v,int l,int w)
{
    node *q = &H[t++];
    q->v = v;
    q->l = l;
    q->w = w;
    q->next = head[u];
    head[u] = q;
}

void bfs(int s)
{
    nn p;
    p.cost = 0;
    p.len = 0;
    p.pos = s;
    que.push(p);
    while (!que.empty())
    {
        nn u = que.top(); que.pop();
        if (u.pos == n)
        {
            ans = u.len;
            break;
        }
        node *q;
        for (q = head[u.pos]; q ; q = q->next)
        {
            nn tp;
            tp.pos = q->v;
            if (u.cost + q->w <= k)
            {
                tp.cost = u.cost + q->w;
                tp.len = u.len + q->l;
                que.push(tp);
            }
        }
    }

}
int main()
{
   //freopen("d.txt","r",stdin);
   int i,a,b,l,w;
   t = 0; ans = inf;
   scanf("%d%d%d",&k,&n,&m);
   for (i = 0; i < m; ++i)
   {
       scanf("%d%d%d%d",&a,&b,&l,&w);
       insert(a,b,l,w);
   }
   bfs(1);
   if (ans != inf) printf("%d\n",ans);
   else printf("-1\n");
   return 0;
}