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

短命女 2023-01-06 11:55 149阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj1729(bfs+优先队列优化）

Jack and Jill <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000M

谁践踏了优雅/ 2024年02月17日 23:55/ 0 赞/ 15 阅读

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

题意：有n 城市，r条路，有k这么多的钱。每条路都有长度和花费两个参数，求从1到n最短且总花费不超过k的长度。思路：优先队列。每次将长度最小的出队，然后判断花费，位超限就将

短命女/ 2023年01月06日 11:55/ 0 赞/ 150 阅读

相关 BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则

青旅半醒/ 2022年10月30日 04:26/ 0 赞/ 207 阅读

相关 Poj 1251 Jungle Roads (邻接表 + 优先队列 + Prime 最小生成树)

突然翻出了几份之前写的代码，拿出来回顾一下。题意：求保持森林中每个村子都有道路相通,且维修所需要的最少money include <iostream> i

素颜马尾好姑娘i/ 2022年08月27日 03:54/ 0 赞/ 185 阅读

相关 CSU oj 1726 你经历过绝望吗？两次！（bfs+优先队列求最短路）（搜索）

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1726 题目大意：给你一个矩阵，有路障栅栏和通路，通路可以直接走

分手后的思念是犯贱/ 2022年08月21日 12:39/ 0 赞/ 5 阅读

相关 BFS广度优先搜索

BFS(Breadth-First Search)，广度优先搜索，又称宽度优先搜索。目的从某个状态出发，彻底地遍历所有可以到达的状态。设s为初始状态，先搜索与

快来打我*/ 2022年07月18日 01:16/ 0 赞/ 255 阅读

相关宽度优先搜索之城市最短路问题

题目描述：有 n 个城市，它们之间的交通情况已知。现在要求根据一个出发点Cs和一个到达点Cd，请编程序，由计算机找到从城市Cs 到 Cd 的一条路径，要求经过城市最少。

ゝ一纸荒年。/ 2022年07月12日 12:44/ 0 赞/ 180 阅读

相关搜索算法之坦克大战（bfs+优先队列）

优先队列：（来自一位大佬的）首先，你需要 include<queue> using namespace std; 这两个头文件。其次，一个

电玩女神/ 2022年06月01日 04:53/ 0 赞/ 224 阅读

相关广度优先搜索（BFS）

BFS是一种图搜索算法，当然这种思想也可以被借鉴到各种其他的算法中。对于图中的所有节点，我们选一个起始点s，然后去发现（遍历）所有从s 点出发能直接到达的点，为了记

蔚落/ 2022年05月15日 00:46/ 0 赞/ 348 阅读

相关 BZOJ 3040: 最短路(road) ( 最短路 )

![042247351018596.png][] 本来想学一下配对堆的...结果学着学着就偏了... 之前 kpm 写过这道题 , 前面的边不理它都能 AC .. 我也懒得

淡淡的烟草味﹌/ 2021年11月10日 12:40/ 0 赞/ 329 阅读