首页 > 代码库 > poj 1724 ROADS (bfs+优先队列)

poj 1724 ROADS (bfs+优先队列)

2024-07-15 09:04:28   227人阅读

题目链接

题意：在有费用k限制的条件下，求从1到n的最短距离，如果最短距离相同求费用最小的，边为有向边，其中可能有

多个相同的源点和目标点，但是距离和费用不同。

分析：用bfs和邻接表来把每一个边搜一下，因为用了优先队列，所以先到n的一定是最小的 。

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <queue> 7 #include <algorithm> 8 #define LL long long 9 const int maxn = 100+50;10 using namespace std;11 int k, n, r;12 struct node13 {14     int v, l, w;15     bool operator < (const node &temp)const16     {17         if(l == temp.l)18             return w > temp.w;  //长度相同按费用排序19         return l > temp.l;20     }21 } ne, pos;22 vector<node>e[maxn];23 24 void bfs()  //里面不能加vis[]数组，因为一个点可能走多次25 {26     int i;27     priority_queue<node>q;28     ne.v = 1;29     ne.l = 0;30     ne.w = 0;31     q.push(ne);32     while(!q.empty())33     {34         pos = q.top();35         q.pop();36         if(pos.v == n)37         {38             printf("%d\n", pos.l);39             return;40         }41         for(i = 0; i < e[pos.v].size(); i++)42         {43             ne.v = e[pos.v][i].v;44             ne.l = pos.l + e[pos.v][i].l;45             ne.w = pos.w + e[pos.v][i].w;46             if(ne.w <= k)47             q.push(ne);48         }49     }50     printf("-1\n");51 }52 int main()53 {54     int i, j;55     while(~scanf("%d", &k))56     {57         scanf("%d%d", &n, &r);58         for(i = 0; i <= n; i++)59             e[i].clear();60         for(i = 0; i < r; i++)61         {62             scanf("%d%d%d%d", &j, &ne.v, &ne.l, &ne.w);63             e[j].push_back(ne);  //跟j相连的加入64         }65         bfs();66     }67     return 0;68 }

 


联系
我们