首页 算法 图论

# 前置文章

  1. Dijkstra 求最短路
  2. bellman-ford 求限制边数的最短路
  3. spfa 求有负权边的最短路
  4. Floyd 求多源汇最短路

# 最短路问题模型

给出一张无向图，有 n 个点和 m 条边，求从 1 号点到 n 号点的最短距离。

# 存图的方法

一般我们使用两种方式存图：

  1. 邻接矩阵：使用一个二维数组 w[i][j] 表示从点 i 到点 j 的距离。
  2. 邻接表：常规做法是使用数组模拟邻接表，具体操作如下：
    // 其中 N 表示点的最大数量，M 表示边的最大数量
    int h[N], w[M], e[M], ne[M], idx;
    // 存储点 a 到点 b 且距离是 w 的一条边
    void add(int a, int b, int w) {
        w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    add(a, b, w);
    // 遍历一个点 u 和所有它能到的点 j。
    dist(h, -1, sizeof h);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
    }
需要注意的一点是，当给出的图是无向图的时候，可以看做是特殊的有向图，既，存在两条边，一条边由 a->b ，另一条边由 b->a 。
# 图论中的最短路算法

稠密图：边数 m 和点数 n 的平方在一个数据级别。
稀疏图：边数 m 和点数 n 在一个数据级别。
# AcWing 1129. 热浪
德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！
他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。
农夫 John 此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。
John 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。
这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。
除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。
每条道路有一个通过费用（包括油费，过路费等等）。
给定一个地图，包含 C 条直接连接 2 个城镇的道路。
每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。
求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。
输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;
第 2 到第 C+1 行：第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。
输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。
数据保证至少存在一条道路。
数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000

输入样例
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出样例
7

# 题目描述
农夫要把牛奶从一个城镇送到另一个城镇，过程中每个城镇都有道路连接，每条道路都有一个通行费用，问 最小的通行费用是多少。
# 题目分析
从题目中，我们可以抽象出这样一个模型：
  1. 送牛奶的路线上共有 T 个城镇，编号为 1~7 ，也就是点的数量 n；
  2. 每个城镇由双向道路连接至少其他两个城镇，说明城镇和道路组成了一个无向图；
  3. 每条道路都有一个过路费用，也就是边的权重；
  4. 求起始城镇到终点城镇的最少需要多少费用，也就是求最短的路径。
如此，我们就找到了一个最短路问题模型。
而根据数据范围：
  1. 点的数量是 2500，那么n2≈6∗106n^2\approx 6*10^6，因此 Dijkstra (朴素版) 可以通过；
  2. 边的数量是 6200，因此 Spfa 可以通过；
  3. m∗logn≈2∗104m*log_n\approx 2*10^4，因此 Dijkstra (堆优化) 也可以通过；
# Code
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int > PII;
// 需要存两倍的边 所以最大边数量需要乘以 2
const int N = 2510, M = 6210 << 1;
int n, m, S, T;
int dist[N];
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 堆优化 Dijkstra
void dij() {
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<>> heap;
    heap.push({0, S});
    dist[S] = 0;
    while (heap.size()) {
        PII t = heap.top();
        heap.pop();
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t.y] + w[i]) {
                dist[j] = dist[t.y] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    for (int i = 1; i <= m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    } 
    dij();
    cout << dist[T] << endl;
    return 0;
}
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2510, M = 6210 << 1;
int n, m, S, T;
int dist[N];
int w[N][N];
bool st[N];
void dij() {
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    for (int i = 1; i <= n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++) {
            if (!st[j] and (t == -1 or dist[t] > dist[j])) t = j;
        }
        st[t] = true;
        for (int j = 1; j <= n; j ++ ) {
            dist[j] = min(dist[t] + w[t][j], dist[j]);
        }
    }
}
int main() {
    cin >> n >> m >> S >> T;
    memset(w, 0x3f, sizeof w);
    for (int i = 1; i <= m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        w[a][b] = w[b][a] = min(w[a][b], c);
    } 
    dij();
    cout << dist[T] << endl;
    return 0;
}
# AcWing 1128. 信使
战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。
指挥部设在第一个哨所。
当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 n 个哨所全部接到命令后，送信才算成功。
因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 k 个信使）。
现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。
输入格式
第 1 行有两个整数 n 和 m，中间用 1 个空格隔开，分别表示有 n 个哨所和 m 条通信线路。
第 2 至 m+1 行：每行三个整数 i、j、k，中间用 1 个空格隔开，表示第 i 个和第 j 个哨所之间存在 双向 通信线路，且这条线路要花费 k 天。
输出格式
一个整数，表示完成整个送信过程的最短时间。
如果不是所有的哨所都能收到信，就输出 - 1。
数据范围
1≤n≤100,
1≤m≤200,
1≤k≤1000

输入样例
4 4
1 2 4
2 3 7
2 4 1
3 4 6

输出样例
11

# 题目描述
有 n 个哨所，第一个哨所作为指挥部，指挥部下达命令后，该命令要传递至所有的 n 个哨所，每个哨所向所有与他相连接的哨所传递信息需要一定的天数。最后求 从指挥部发出命令到通知完所有哨所 最少需要多少天。
# 题目分析
抽象出本题的模型：
  1. 指挥部 -> 源点；
  2. 哨所 -> 点；
  3. 花费的天数 -> 权重；
  4. 目标： 从源点出发求抵达所有点的最短距离的最大值。
所以，我们只要求出源点到所有点所需要的最短距离，然后找出其中的最大值就可以了。
分析时间复杂度，发现本题时间复杂度较小，使用任意一种最短路算法均可。
# Code
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110, M = 20010;
int n, m, res;
int h[N], ne[M], e[M], w[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// Dijkstra（堆优化）
void dij() {
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    dist[1] = 0;
    while (q.size()) {
        PII t = q.top();
        q.pop();
        if (st[t.y]) continue;
        st[t.y] = true;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t.y] + w[i]) {
                dist[j] = dist[t.y] + w[i];
                q.push({dist[j], j});
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dij();
    for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);
    if (res == 0x3f3f3f3f) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}
# AcWing 1127. 香甜的黄油
农夫 John 发现了做出全威斯康辛州最甜的黄油的方法：糖。
把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。
当然，他将付出额外的费用在奶牛上。
农夫 John 很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。
他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫 John 知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。
给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。
数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式
第一行：三个数：奶牛数 N，牧场数 P，牧场间道路数 C。
第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。
第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场 A、B，两牧场间距 D，当然，连接是双向的。
输出格式
共一行，输出奶牛必须行走的最小的距离和。
数据范围
1≤N≤500,
2≤P≤800,
1≤C≤1450,
1≤D≤255

输入样例
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

输出样例
8

# 题目描述
有一些奶牛，他们分布在不同的牧场，牧场间通过到道路相连接，每个道路长度不一，目标是找到一个牧场，使得所有其他牧场的奶牛走到这个牧场的 距离总和 最小。
# 题目分析
抽象一下本题的模型：
  1. 奶牛们所在的牧场：点；
  2. 牧场间有道路相连接：边；
  3. 牧场之间的距离：边的权重；
    求找到一个点，使得 所有其他点的奶牛走到它的 权重之和 最小。
因为目标是所有奶牛走到目标牧场的 距离之和 最小，所以我们可以 遍历所有牧场，假设当前牧场是 i ，对于每个 i ，都求出 所有奶牛走到 i 的 距离之和，这样自然就知道选择哪个牧场是最好的。
求所有奶牛到点 i 的距离之和，可以以点 i 作为源点，求 i 到所有奶牛的最小距离，然后累加起来。
观察一下数据范围，看一下可以用什么算法：
  1. 奶牛数量 N 是 500，边的数量是 1450，点的数量 800，每个点都跑一遍 Dijkstra（堆优化）的时间复杂度是800∗log(500)∗1450≈3∗106800*log(500)*1450\approx 3*10^6，因此可以使用。
  2. 每个点跑一遍 Spfa 的时间复杂度是800∗1450≈1∗106800*1450\approx 1*10^6，因此也可以用。
# Code
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int n, p, m, cows[N], dist[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dij(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, s});
    dist[s] = 0;
    while (q.size()) {
        PII t = q.top();
        q.pop();
        if (st[t.y]) continue;
        st[t.y] = true;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > t.x + w[i]) {
                dist[j] = t.x + w[i];
                q.push({dist[j], j});
            }
        }
    }
    int ans = 0;
    // 计算所有奶牛到当前点的最短距离之和
    for (int i = 1; i <= n; i ++ ) {
        if (dist[cows[i]] == INF) return INF;
        ans += dist[cows[i]];
    }
    return ans;
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> p >> m;
    for (int i = 1; i <= n; i ++ ) cin >> cows[i];
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    // 遍历所有的点，找到结果。
    int res = INF;
    for (int i = 1; i <= p; i ++ ) res = min(res, dij(i));
    cout << res << endl;
    return 0;
}
# AcWing 1126. 最小花费
在 n 个人中，某些人的银行账号之间可以互相转账。
这些人之间转账的手续费各不相同。
给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。
输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。
以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 (z<100)。
最后一行输入两个正整数 A,B。
数据保证 A 与 B 之间可以直接或间接地转账。
输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。
精确到小数点后 8 位。
数据范围
1≤n≤2000,
m≤105
输入样例
3 3
1 2 1
2 3 2
1 3 3
1 3

输出样例
103.07153164

# 题目描述
有 n 个人，其中某些人的银行账号可以互相转账，转账需要手续费，而每个转账需要的手续费是不同的，给出 A 和 B，要问要使得转账后 B 收到 100 块钱，那么 A 最开始最少要发出多少钱。
# 题目分析
抽象出本题的模型：
  1. 每个人的银行账号 -> 点；
  2. 两个账号可以互相转账 -> 两点之间连一条边；
  3. 转账的手续费 -> 边的权重；
    目标是求 从 A 点到 B 点，使得 B 收到 100 块钱，所需要的最短路径。
本题其实也是个比较标准的最短路模型，只是在其中加入了小数类型的操作，也就是边的权值不再是整数，而是小数。
假设 a 点转账 x 元，那么 b 点收到就是 x * (1-z%) 元。
如果经过的线路是 w[1]，w[2]，...，w[k] 。
那么假设初始转账为 A 结果就是 A * w [1] * w [2] * .... * w [k] = 100
我们想让 A 最小， 就要让 w[1] * w[2] * ... * w[k] 最大，也就是扣掉手续费后剩下的钱 更多。
本题的数据范围很小，几种算法可以任意选择。
# Code
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<double, int> PDI;
const int N = 2010, M = 200010;
int n, m, start, ed;
double dist[N];
bool st[N];
int h[N], e[M], ne[M], idx;
double w[M];
void add(int a, int b, double c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dij(int s) {
    priority_queue<PDI> q;
    q.push({1, s});
    dist[s] = 1;
    while (q.size()) {
        PDI t = q.top();
        q.pop();
        if (st[t.y]) continue;
        st[t.y] = true;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < t.x * w[i]) {
                dist[j] = t.x * w[i];
                q.push({dist[j], j});
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        // 本题的权重为 扣掉手续费后剩下的。
        double z = 1 - c * 0.01;
        add(a, b, z), add(b, a, z);
    }
    cin >> start >> ed;
    dij(start);
    printf("%.8lf", 100 / dist[ed]);
    return 0;
}
# AcWing 920. 最优乘车
H 城是一个旅游胜地，每年都有成千上万的人前来观光。
为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。
每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。
现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。
写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。
输入格式
第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。
从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。
输出格式
共一行，如果无法乘巴士从饭店到达 S 公园，则输出 NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。
数据范围
1≤M≤100,
2≤N≤500

输入样例
3 7
6 7
4 7 3 6
2 1 3 5

输出样例
2

# 题目描述
一个人来 H 城游玩，H 城的旅游公司设置了很多公交线路，每条公交线路可以到达一些不同的地点，他想去 S 公园，如果他所在的地方没有直达的公交，则他到达公园需要换乘多个不同的线路，本题的问题是：他至少需要换乘多少次才能到达公园。
# 题目分析
本题和前面的题目不同的地方在于，本题并不是问路线的距离，而是问需要换乘的最少次数。
对于每条公交线路，该线路上的任意车站都能沿着该线路到达后面的任意车站，因此一条路线上的任意两点之间权值都是 1，表示只乘坐了一量车。
而换乘次数，就可以认为是乘车数量减一。
而根据前面的文章，当权重固定为 1 的时候，我们可以直接使用 BFS 来求最短路。
所以问题就转换为用 BFS 求出起点到终点最少使用的车辆数。
# Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
#define x first
#define y second
using namespace std;
const int N = 510, M = 110;
int n, m;
bool g[N][N];
int stop[N];
int dist[N];
int q[N];
// BFS 求最短距离
void bfs() {
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    q[0] = 1;
    dist[1] = 0;
    while (hh <= tt) {
        int t = q[hh ++ ];
        //dijstra 思路
        for (int i = 1; i <= n; i ++ ) {
            if (g[t][i] and dist[i] > dist[t] + 1) {
                dist[i] = dist[t] + 1;
                q[ ++ tt] = i;
            }
        }
    }
}
int main () {
    cin >> m >> n;
    string line;
    getline(cin, line); // 这里的操作是读掉回车
    while (m -- ) {
        getline(cin, line);
        stringstream ssin(line); // 这是读一行
        int cnt = 0, p;
        while (ssin >> p) stop[cnt ++ ] = p;
        // 每个路线的任意两站之间距离都是 1 因为是同一辆车 没换车
        for (int j = 0; j < cnt; j ++ ) 
            for (int k = j + 1; k < cnt; k ++ )
                // 表示 j 到 k 可以连一条边
                g[stop[j]][stop[k]] = 1;
    }
    bfs();
    if (dist[n] == 0x3f3f3f3f) puts("NO");
    else cout << max(dist[n] - 1, 0) << endl;
    return 0;
}
# AcWing 903. 昂贵的聘礼
年轻的探险家来到了一个印第安部落里。
在那里他和酋长的女儿相爱了，于是便向酋长去求亲。
酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。
探险家拿不出这么多金币，便请求酋长降低要求。
酋长说：” 嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 8000 金币。如果你能够弄来他的水晶球，那么只要 5000 金币就行了。”
探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。
探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。
不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。
探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。
另外他要告诉你的是，在这个部落里，等级观念十分森严。
地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。
他是一个外来人，所以可以不受这些限制。
但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。
因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从 1 开始进行编号，酋长的允诺也看作一个物品，并且编号总是 1。
每个物品都有对应的价格 P，主人的地位等级 L，以及一系列的替代品 Ti 和该替代品所对应的” 优惠” Vi。
如果两人地位等级差距超过了 M，就不能” 间接交易”。
你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
输入格式
输入第一行是两个整数 M，N，依次表示地位等级差距限制和物品的总数。
接下来按照编号从小到大依次给出了 N 个物品的描述。
每个物品的描述开头是三个非负整数 P、L、X，依次表示该物品的价格、主人的地位等级和替代品总数。
接下来 X 行每行包括两个整数 T 和 V，分别表示替代品的编号和” 优惠价格”。
输出格式
输出最少需要的金币数。
数据范围
1≤N≤100,
1≤P≤10000,
1≤L,M≤N,
0≤X<N

输入格式
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

输出格式
5250

# 题目描述
很有趣的一个题目，冒险家想娶酋长的女儿，聘礼是 10000 个金币，但是如果能弄到大祭司的皮袄那么就只需要 8000 金币，如果弄来大祭司的水晶球那么就只需要 5000 金币，要注意的是皮袄和水晶球只能用一个。而大祭司的水晶球或者皮袄同样有它们的价格，并且也可以使用其他人的物品来降低价格。问题是 最少需要多少金币可以支付聘礼。
# 题目分析
本题比前面的题目明显要难上一个档次，我们先想办法抽象出本题的模型：
  1. 如果把 a 物品看做一个点，那么如果 a 物品能通过 b 物品换到，我们就建立一条有向边 b -> a ，边的权重就是仍然需要支付的金币。比如最终目标 “聘礼”，可以通过大祭司的水晶球加上 5000 金币换到，那么就可以建立一条边由 “水晶球” 指向 “聘礼”，这条边的权重就是 5000。
  2. 注意，通过上面的方式见图，我们是没有考虑到每个物品直接购买的这种情况的。这种情况，我们可以建立一个 **“超级源点”**，即，这个源点不是任何物品，它只作为一个起点，它与所有的点都连有一条边，边的权重就是直接购买这个点所代表物品的价格。
通过上面的方法建立出整张图之后，我们神奇的发现，本题其实就是求以超级源点为起点，以 “聘礼” 为终点，从起点到终点的最短路径。
下面的图是使用上述的建图方式，对给定实例建图的结果。
本题除了建图之外，还有一个点需要注意，既本题中每一个点都有一个地位值，超过一定地位值则不可以进行贸易。
那么该限制下，我们以酋长为中心，枚举所有可行的贸易值范围即可，在这些可行范围中求出最少的花费。
本题中，点数最多是 100，每个点最多又可能连出 100 条边，所以边数量最多是 10000，整体的数据范围不是很大，因此三种最短路做法都可以。
# Code
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110, M = 20010;
int n, m;
int dist[N], level[N];
bool st[N];
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 堆优化 dijkstra 其中 down 和 up 表示区间的上下界
int dijkstra(int down, int up) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 0});
    dist[0] = 0;
    while (q.size()) {
        PII t = q.top();
        q.pop();
        if (st[t.y]) continue;
        st[t.y] = true;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            // 连接到的点一定要在区间内
            if (level[j] >= down and level[j] <= up and dist[j] > t.x + w[i]) {
                dist[j] = t.x + w[i];
                q.push({dist[j], j});
            }
        }
    }
    return dist[1];
}
int main() {
    memset(h, -1, sizeof h);
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ) {
        int p, cnt;
        cin >> p >> level[i] >> cnt;
        // 超级源点 0 到每个点都有一条有向边
        // 权值是直接购买物品的所需价格
        add(0, i, p);  
        while (cnt -- ) {
            int id, cost;
            cin >> id >> cost;
            add(id, i, cost);
        }
    }
    // 可行区间为 [level [1] - m, level [1]]
    int res = 0x3f3f3f3f;
    for (int i = level[1] - m; i <= level[1]; i ++ ) 
        res = min(dijkstra(i, i + m), res);
    cout << res << endl;
    return 0;
}
未完待续