Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 48028 Accepted: 14310 Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。 为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。 Input 输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和"优惠价格"。 Output 输出最少需要的金币数。 Sample Input 1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0 Sample Output 5250 解题思路：这道题总体来说不难，很明显用的是最短路算法，我用的是dijkstra算法,但是有几个细节要注意
1：要枚举人的等级，用两个for循环，把找的每一次的最短路里的等级限定在l+m 这个范围，（会找n次）；
2：需要进行n次dijkstra，因为我们不知道起点在哪里，只知道终点(酋长）在哪里，所以每个点都有可能为起点。
3：这道题每个边有权值，每个点也有权值，所以对d[i]初始化要用for循环，并且不是为0，而是每个宝物的初始价格
ps:本来想用dijkstra+priority_queue呢，奈何想了一个下午，写错了，
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int MAXN = 105; const int INF = 0x3f3f3f3f; int price[MAXN]; //价格数组 int d[MAXN]; //最短距离数组 int cost[MAXN][MAXN]; //邻接矩阵 bool used[MAXN]; //标记数组 若该顶点可以用则为true void dijkstra(int n) //传入顶点个数 { for (int i = 0; i < n; i++) { //对每次dijkstra都要进行d[i]的初始化，因为每次都相当于一共新的起点，新的情况 d[i] = price[i]; } int k = -1; while (true) { k = -1; for (int i = 0; i < n; i++) { //从上未使用过的顶点中选择一个距离最小的顶点 if (used[i] && (k == -1 || d[k] > d[i])) { k = i; } } if (k == -1) { break; } used[k] = false; for (int i = 0; i < n; i++) { if(used[i]) { //因为有等级的限制，所以必须有这个判断 d[i] = min(d[i], d[k] + cost[k][i]); } } } } int main() { //初始化 memset(cost, INF, sizeof(cost)); memset(d, INF, sizeof(d)); int m, n; //地位等级差距限制和物品的总数 int level[MAXN]; //地位等级数组 cin >> m >> n; int l, p, x; 该物品的价格、主人的地位等级和替代品总数 for (int i = 0; i < n; i++) { cin >> p >> l >> x; level[i] = l; price[i] = p; int t,v; 替代品的编号和"优惠价格"。 for (int j = 0; j < x; j++) { cin >> t >> v; cost[t - 1][i] = v; } } int l_limit; int minD = INF; //最短距离 for (int i = 0; i < n; i++) { //n次dijkstra i是每次的起点 l_limit = level[i]; for (int j = 0; j < n; j++) { //对每个点的进行检查，看是否符合等级的限制 if (level[j] - l_limit > m || level[j] < l_limit) { used[j] = false; } else { used[j] = true; } } dijkstra(n); minD = min(minD, d[0]); } cout << minD << endl; return 0; }2019.3.16：这些天在准备复试的，所以就看看了原先的算法题，对这道题我有用优先队列做了一遍，但是POJ提交出错，很无奈，只能先把代码贴到这里，思路跟上面的一样，所以我就没有写注释。如果有大佬看出错误请给我留言 谢谢
#include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <vector> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 105; struct Edge { int to, cost; }; typedef pair<int, int> P; vector<Edge> G[MAXN]; int d[MAXN]; int price[MAXN]; int level[MAXN]; bool used[MAXN]; void dijkstra(int n, int sta) { priority_queue<P, vector<P>, greater<P> > que; for (int i = 0; i <n ; i++) { if (used[i]) { d[i] = price[i]; que.push(P(d[i], i)); } } while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) { continue; } for (int i = 0; i < G[v].size(); i++) { if (used[i]) { Edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } } int main() { memset(d, INF,sizeof(d)); int m, n; cin >> m >> n; for (int i = 0; i < n; i++) { int l, p, x; cin >> p >> l >> x; level[i] = l; price[i] = p; for (int j = 0; j < x; j++) { int t, v; Edge e; cin >> t >> v; e.to = i; e.cost = v; G[t - 1].push_back(e); } } int ans = INF; for (int i = 0; i < n; i++) { int l_limit = level[i]; for(int j = 0; j < n; j++) { if (level[j] - l_limit > m || level[j] < l_limit) { used[j] = false; } else { used[j] = true; } } dijkstra(n, i); ans = min(ans, d[0]); } cout << ans << endl; return 0; }
