72 lines
2.3 KiB
C++
72 lines
2.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef pair<int, int> PII;
|
||
const int N = 110;
|
||
const int M = N * N; // 边数最多有n^2,这是顶天设置，此处与传统的题目不，一般的M= N<<1，此题目没有明确给出边数上限，直接认为N^2
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
int h[N], e[M], ne[M], w[M], idx;
|
||
void add(int a, int b, int c) {
|
||
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
||
}
|
||
|
||
int dis[N]; // 单源最短路径
|
||
bool st[N]; // 配合Dijkstra用的是否出队过
|
||
|
||
int L[N]; // 每个节点的等级
|
||
int n, m; // n个物品，m表示等级差距限制
|
||
|
||
int dijkstra(int l, int r) {
|
||
memset(dis, 0x3f, sizeof dis);
|
||
memset(st, 0, sizeof st);
|
||
priority_queue<PII, vector<PII>, greater<PII>> q;
|
||
// 距离，节点号
|
||
q.push({0, 0}); // 超级源点
|
||
dis[0] = 0;
|
||
|
||
while (q.size()) {
|
||
auto t = q.top();
|
||
q.pop();
|
||
int u = t.second;
|
||
if (st[u]) continue;
|
||
st[u] = true;
|
||
|
||
for (int i = h[u]; ~i; i = ne[i]) {
|
||
int v = e[i];
|
||
// 枚举边时，只处理等级在指定范围内
|
||
if (L[v] < l || L[v] > r) continue;
|
||
|
||
if (dis[v] > dis[u] + w[i]) {
|
||
dis[v] = dis[u] + w[i];
|
||
q.push({dis[v], v});
|
||
}
|
||
}
|
||
}
|
||
return dis[1];
|
||
}
|
||
|
||
int main() {
|
||
memset(h, -1, sizeof h); // 初始化邻接表
|
||
cin >> m >> n; // m:表示地位等级差距限制，n:物品的总数
|
||
|
||
for (int i = 1; i <= n; i++) { // 枚举每个节点
|
||
int p, l, cnt; // 价格 等级 替代品数目
|
||
cin >> p >> L[i] >> cnt;
|
||
|
||
add(0, i, p); // 虚拟源点0, 0获取i号物品，需要p这么多的金币
|
||
|
||
while (cnt--) { // 读入物品i的替代品
|
||
int u, v; // 替代品的编号 和 优惠价格
|
||
cin >> u >> v; // u:替代品编号，v:收到替代品后的收费价格
|
||
add(u, i, v); // 从替代品向可替代品引一条长度为v的边
|
||
}
|
||
}
|
||
// 预求最小，先设最大
|
||
int res = INF;
|
||
// 枚举区间范围进行多次求最小路径
|
||
for (int i = L[1] - m; i <= L[1]; i++)
|
||
res = min(res, dijkstra(i, i + m));
|
||
// 输出结果
|
||
cout << res << endl;
|
||
return 0;
|
||
} |