昂贵的聘礼(SPFA最短路)

2024-06-14 16:18
文章标签 短路 spfa 聘礼 昂贵

本文主要是介绍昂贵的聘礼(SPFA最短路),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最短路问题,建图(有向图),以1点为源点,枚举等级的限制,即每次都用spfa 求得1点到其他能够到达的点(由于等级的限制,在一次spfa中可能并不是所有的点都能够到达),最后求出所需最小费用。


#include <iostream>
#include <queue>
#include <cstring>
using namespace std;#define Max 110
#define levelInit -1
#define visitInit false
#define peopleInit -1
#define priceInit 9999999
#define start 1int peopleToPeople[Max][Max];
int changePrice[Max];
int level[Max];
bool visit[Max];
int price[Max];int n; int m;
queue< int > Q;void init(){    int p      = priceInit;int l      = levelInit;int num    = 0;int index  = 0;int indexP = 0;memset( level,          levelInit,  sizeof( level ) );memset( visit,          visitInit,  sizeof( visit ) );memset( peopleToPeople, peopleInit, sizeof( peopleToPeople ) );memset( changePrice,    priceInit,  sizeof( changePrice ) );memset( price,          priceInit,  sizeof( price ) );for( int i = 1; i <= n; ++i ){cin >> p >> l >> num;level[i] = l;price[i] = p;for( int j = 1; j <= num; ++j ){cin >> index >> indexP;peopleToPeople[i][index] = indexP;            }}
}void SPFA(){visit[start]       = true;changePrice[start] = 0;Q.push( start );while( !Q.empty() ){int index = Q.front();Q.pop();visit[index] = false;for( int i = 1; i <= n; ++i ){if( peopleToPeople[index][i] != peopleInit && peopleToPeople[index][i] + changePrice[index] < changePrice[i] ){changePrice[i] = peopleToPeople[index][i] + changePrice[index];if(visit[i] == false){visit[i] = true;Q.push( i );                                        }}}}
}int main(){cin >> m >> n;init();SPFA();const int lev = level[start];int minPrice  = priceInit;for( int i = 1; i <= n; ++i ){changePrice[i] += price[i];if( minPrice > changePrice[i] && lev - level[i] <= m && lev - level[i] >= 0) minPrice = changePrice[i];}cout << minPrice << endl;return 0;
}


这篇关于昂贵的聘礼(SPFA最短路)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1060892

相关文章

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3169 spfa 差分约束

题意: 给n只牛,这些牛有些关系。 ml个关系:fr 与 to 牛间的距离要小于等于 cost。 md个关系:fr 与 to 牛间的距离要大于等于 cost。 隐含关系: d[ i ] <= d[ i + 1 ] 解析: 用以上关系建图,求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码: #include <iostream>#include

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i

poj 2449 第k短路 A* + spfa

poj 2449: 题意: 给一张有向图,求第k短路。 解析: A* + spfa。 一下转自:http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式:f(x)=g(x)+h(x);对h(x)进行设计,根据定义h(x)为当前的x点到目标点t所需要的实际距

poj 3259 最短路负环

John的农场里N块地,M条路连接两块地,W个虫洞,虫洞是一条单向路,会在你离开之前把你传送到目的地,就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。简化下,就是看图中有没有负权环。有的话就是可以,没有的话就是不可以了。 import java.io.BufferedReader;import java.io.InputStream;

POJ1724最短路

n个点,拥有总的价值money m条边(u,v,len ,cost),长度len,代价cost 求不超过money的代价条件下最短路。 public class Main {public static void main(String[] args) {new Task().solve();}}class Task {InputReader in = new InputReader