poj-1724(bfs+优先队列)

题意：有向图，给你m条边，每条边有两个权值，路径长和通过这条路径的花费，问你在不超过k花费的前提下，最短的路径从1走到n

解题思路：因为边数很少，我们可以直接用暴力每条边的方式来找最小的路径长，也就是用一个优先队列，每次弹出路径最短的边，计算当前花费和下条边的花费如果小于k，那么这条边就可行。

很多博客写是迪杰斯特拉+heap，我觉得没有松弛过程的应该算不上单元最短路的写法把（QAQ）;

代码：

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<queue>

#define maxn 100000

#define inf 1e9

using namespace std;

struct Edge

{

    int next;

    int to;

    int w;

    int c;

}edge[maxn];

struct node

{

    int num;

    int dist;

    int cost;

    node(int _num=0,int _dist=0,int _cost=0):num(_num),dist(_dist),cost(_cost){}

    bool operator < (const node &a) const

	{

		return a.dist<dist;

	}

};

int head[maxn];

int cnt;

int dist[maxn];

int k,n,m;

void add(int u,int v,int w,int c)

{

    edge[cnt].to=v;

    edge[cnt].w=w;

    edge[cnt].c=c;

    edge[cnt].next=head[u];

    head[u]=cnt++;

}

int dij(int x)

{

    int ans=-1;

    node u,v;

    priority_queue<node>que;

    que.push(node(x,0,0));

    while(!que.empty())

    {

        node u=que.top();

        que.pop();

        int now=u.num;

        if(now==n)

        {

            ans=u.dist;

            return ans;

            break;

        }

        for(int i=head[now];i!=-1;i=edge[i].next)

        {

            if(u.cost+edge[i].c<=k)

            {

                v.num=edge[i].to;

                v.dist=u.dist+edge[i].w;

                v.cost=u.cost+edge[i].c;

                que.push(v);

            }

        }

    }

    return ans;

}

int main()

{

    int x,y,w,c;

    while(cin>>k>>n>>m)

    {

        memset(head,-1,sizeof(head));

            cnt=0;

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

        {

            cin>>x>>y>>w>>c;

            add(x,y,w,c);

        }

        cout<<dij(1)<<endl;

    }

}