本文主要是介绍昂贵的聘礼(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最短路)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!