题意： 无向图  每条边有长度和费用两个属性  求从点1到点n 在花费不超过 k 的情况下的最短路径

BFS  使用优先队列 长度短的优先出列      题解上的方法没看懂  不知道怎么用链表维护 .....

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

struct node

{

    int dd, pp, len;

    node(int d, int p, int le)

    {

        dd = d, pp = p, len = le;

    }

    bool operator < (const node & p) const

    {

        if(len != p.len)

            return p.len < len;

        return p.pp < pp;

    }

};

vector<int> gto[110], cost[110], Len[110];

bool vis[110][10010];

int main()

{

    int T,N,K,R,ans;

    scanf("%d",&T);

    while(T--)

    {

        ans = -1;

        memset(vis, false, sizeof(vis));

        scanf("%d%d%d",&K,&N,&R);

        for(int i = 1; i <= N; i++)

        {

            gto[i].clear(), cost[i].clear(), Len[i].clear();

        }

        for(int i = 0; i < R; i++)

        {

            int s,d,l,t;

            scanf("%d%d%d%d",&s,&d,&l,&t);

            gto[s].push_back(d), Len[s].push_back(l), cost[s].push_back(t);

        }

        priority_queue<node> q;

        q.push(node(1, 0, 0));

        while(!q.empty())

        {

            node u = q.top();

            q.pop();

            if(u.dd == N)

            {

                ans = u.len;

                break;

            }

            if(!vis[u.dd][u.pp])

            {

                vis[u.dd][u.pp] = true;

                int p = gto[u.dd].size();

                for(int i = 0; i < p; i++)

                {

                    int de = gto[u.dd][i];

                    int _len = u.len + Len[u.dd][i];

                    int co = u.pp + cost[u.dd][i];

                    if(co <= K)

                        q.push(node(de, co, _len));

                }

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}