Poj 1724 ROADS (搜索最短路 BFS优先队列)-蒲公英云

Poj 1724 ROADS (搜索最短路 BFS优先队列)

短命女 2023-01-06 11:55 241阅读 0赞

题意：有n 城市，r条路，有k这么多的钱。每条路都有长度和花费两个参数，求从1到n最短且总花费不超过k的长度。

思路：优先队列。每次将长度最小的出队，然后判断花费，位超限就将后继点入队。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n,k,r,e;
int head[105];
struct Edges
{
    int v,c,l,next;
}edge[10005];
struct Node
{
    int u,cost,len;
    Node (int _u,int _c, int _l)
    {
        u=_u,cost=_c,len=_l;
    }
    bool operator < (const Node& b) const 
    {
        return len>b.len;
    }
};
void Addedge (int u, int v, int len, int cost)
{
    edge[e].next = head[u];
    edge[e].v = v;
    edge[e].l = len;
    edge[e].c = cost;
    head[u] = e++;
}
int Deal ()
{
    priority_queue<Node> q;
    q.push(Node(1,0,0));
    while (!q.empty())
    {
        Node temp = q.top();
        q.pop();
        if (temp.u == n)
            return temp.len;
        for (int i=head[temp.u];i != -1; i=edge[i].next)
            if (temp.cost + edge[i].c <= k)
                q.push (Node(edge[i].v,temp.cost+edge[i].c,temp.len+edge[i].l));
    }
    return -1;
}
int main ()
{
    scanf("%d%d%d",&k,&n,&r);
    e=0;
    memset(head,-1,sizeof(head));
    for (int i=0; i<r;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        Addedge(a,b,c,d);
    }
    printf("%d\n",Deal ());
    return 0;
}