昂贵的聘礼

发表于 | Edited on | 分类于 | 次阅读

题目来源：http://bailian.openjudge.cn/practice/1062/

解题思路：

- 假设冒险家自身是第0号物品，可以将这道题目理解为经过一系列的物品的交换，花费最少的金币换得酋长的1号物品。
-将其看作图论，建图的时候，每次遇到一个物品及其原价，可以设置0号物品到该物品的距离为该物品的价值。即表明冒险家直接购买物品需要花费的金币。
- 对于某个物品的替代品，可以设置为替代品的编号到原物品编号之间的花费为“优惠价格”，无论经过多少次交换，最后必须和酋长进行交换，而酋长对冒险家交换过的物品等级有限制，假设酋长的地位为Q，可以忍受的等级差距为M，那么就可以枚举等级差距为M的等级范围。即[Q-M, Q],[Q-M+1, Q+1]...[Q, Q+M]。
- 将所有等级限制范围内可以交换花费的最小金币求取最小值，即为最少花费的金币。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <queue>
#include <cstdio>

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef const int CI;

struct Gift {
	int level;
	int value;
	Gift(int l = 0, int v = 0) :level(l), value(v) {};
};

struct Edge {
	int from, to;
	int dis;
	Edge(int f, int t, int d) :from(f), to(t), dis(d) {}
	bool operator<(const Edge& e)const { return this->dis > e.dis; };
};

// dijkstra 算法，low和high分别表示等级范围
int solution(const VVI& graph, const vector<Gift>& gift, CI low, CI high) {
	VI dis(graph.size(), INT_MAX);
	dis[0] = 0;
	priority_queue<Edge> myQueue;
    // 每次加入边的时候考虑等级差距
	for (int i = 1; i < graph.size(); ++i){
		if (gift[i].level >= low&&gift[i].level <= high)
			dis[i] = graph[0][i];
		else
			dis[i] = INT_MAX;
		myQueue.push(Edge(0, i, dis[i]));
	}
	VI visit(graph.size(), 0);
	visit[0] = 1;
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		dis[e.to] = e.dis;
		for (int j = 1; j < graph.size(); ++j) {
            // 每次加入边的时候考虑等级差距
			if (visit[j] == 0 && gift[j].level >= low&&gift[j].level <= high&&dis[e.to] < dis[j] - graph[e.to][j])
				myQueue.push(Edge(e.to, j, dis[e.to] + graph[e.to][j]));
		}
	}
	return dis[1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int M, N;
	while (cin >> M >> N) {
		vector<Gift> gift(N + 1);
		
		VVI graph(N + 1, VI(N + 1, INT_MAX));
		for (int i = 0; i < N + 1; ++i)
			graph[i][i] = 0;
		
		for (int i = 1; i <= N; ++i) {
			int alter;
			cin >> gift[i].value >> gift[i].level >> alter;
			graph[0][i] = gift[i].value;
			for (int j = 0; j < alter; ++j) {
				int x, y;
				cin >> x >> y;
				graph[x][i] = y;
			}
		}
		CI L = gift[1].level;
		int ans = INT_MAX;
		for (int i = 0; i <= M; ++i) {
			int tmp = solution(graph, gift,  L - i, L - i + M);
			ans = min(ans, tmp);
		}
		printf("%d\n", ans);
	}
	return 0;
}