前几道是最短路，最后一道是拓扑排序
最短路没啥好讲的其实（）建议是把dijkstra算法背下来就行（可以参考接下来代码里的dijkstra函数，把这个模板背下来再改改，机考绝对没问题了）
课上的dijkstra算法是不带优化的，求解单源最短路复杂度是O(n^2)，接下来模板里给的是带单调队列优化的，也就是通过一种特殊的数据结构，使得在n个邻居结点当中查找最近的那条边的过程从O(n)降到了log级别，原理可以参考堆优化版Dijkstra算法，如果只想应对机考，把模板背下来就可以了
课上还提了floyd算法，用三个循环求解图上所有点与点之间的最短路，复杂度O(n^3)，如果数据范围给的结点数量大于100，基本上就会超时（如果是dijkstra而且只求单源最短路，复杂度O(n^2)，完全可以应对10000的数据量），但floyd算法的好处是非常容易理解且非常好写，假如你马上就要机考，而且最短路一点没学，看了dijkstra算法感觉背不下来，那么建议快速地学一下floyd算法，考到最短路别管什么数据范围，闭眼敲这个算法的模板，虽然大概率超时，但估计能得到60/100的分，比只输出样例要高不少
极速学习教程：Floyd算法
只需要看第一部分，而且记住那三个循环就可以了
快速记忆方法：
- 建个二维数组
G[n][n]，G[i][j]表示点i到点j的最短距离 - 把二维数组初始化为无穷大，表示一开始每两个点都不可达（可以用
#define INF 0x3f3f3f3f实现） - 每次读入一条
u和v之间的边，就把G[u][v]设成这条边的长度 - 把所有
G[i][i]（i从1到n都设成0，表示一个点到自己肯定没有距离） - 敲这三个循环，都是从1到n，顺序是
k,i,j
其实很好理解，相当于是先把每个点for (int k = 1;k <= n;k++) { for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { G[i][j] = min(G[i][j],G[i][k] + G[k][j]); } } }k设为“中转站”，再跑两个循环，判断对每一对i和j，是原先的路更短，还是先从i走到k，再从k走到j更短
1059. 路由器
n在100以内，而且求多源最短路，建议floyd，输入给的是IP，可以用一个map将字符串转化为代表结点的数字，然后套上述的模板
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int main() {
int n,m;
cin >> n >> m;
int G[n+1][n+1];
memset(G,INF,sizeof(G));
map<string,int> id;
int c = 1;
int t,time;
string ip1,ip2;
while(m--) {
cin >> ip1 >> ip2 >> time;
if (!id[ip1]) {
id[ip1] = c;
c++;
}
if (!id[ip2]) {
id[ip2] = c;
c++;
}
int u = id[ip1];
int v = id[ip2];
G[u][v] = G[v][u] = time;
}
for (int i = 1;i <= n;i++) {
G[i][i] = 0;
}
for (int k = 1;k <= n;k++) {
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
}
}
}
cin >> t;
while (t--) {
cin >> ip1 >> ip2;
int id1 = id[ip1];
int id2 = id[ip2];
if (G[id1][id2] == INF) {
cout << -1 << endl;
} else
cout << G[id1][id2] << endl;
}
return 0;
}1060. 最短路径
dijkstra算法模板题，输出最短路径需要维护一个prev数组，prev[u]表示最短路径里u的前驱结点是谁（每次更新最近邻居的时候顺便更新这个），最后倒序输出prev数组即可
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
void dijkstra(int start,int end,int n,vector<vector<pair<int,int>>>& G) {
vector<bool> visited(n+1,false);
vector<int> d(n+1,INF);
vector<int> prev(n+1,-1);
vector<int> count(n+1,0);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
d[start] = 0;
count[start] = 1;
pq.push(make_pair(0,start));
while (!pq.empty()) {
int w = pq.top().first;
int u = pq.top().second;
pq.pop();
if (visited[u]) {
continue;
}
visited[u] = true;
for (auto& edge:G[u]) {
int ww = edge.first;
int v = edge.second;
if (d[v] > d[u] + ww) {
d[v] = d[u] + ww;
pq.push({d[v],v});
prev[v] = u;
count[v] = count[u];
} else if (d[v] == d[u] + ww) {
count[v] += count[u];
}
}
}
if (d[end] == INF) {
printf("%d\n%d\n%d",-1,0,-1);
} else {
cout << d[end] << endl;
cout << count[end] << endl;
vector<int> ans;
for (int tmp = end;tmp != -1;tmp = prev[tmp]) {
ans.push_back(tmp);
}
reverse(ans.begin(),ans.end());
for (int e:ans) {
cout << e << " ";
}
}
}
int main() {
int n,m;
cin >> n >> m;
int u,v,w;
vector<vector<pair<int,int>>> G(n+1);
while (m--) {
cin >> u >> v >> w;
G[u].push_back(make_pair(w,v));
G[v].push_back(make_pair(w,u));
}
dijkstra(1,n,n,G);
return 0;
}1061. Arbitrage
题意
套利（Arbitrage） 是指利用货币汇率的差异，通过一系列货币兑换，将一种货币转换为更多的同种货币。例如：
1 美元可以兑换 0.5 英镑。
1 英镑可以兑换 10.0 法郎。
1 法郎可以兑换 0.21 美元。
通过这一系列兑换，1 美元可以变成0.5×10.0×0.21=1.05 美元，获得 5% 的利润。
任务是编写一个程序，输入货币汇率表，判断是否存在套利机会。
依旧floyd算法，把每种货币作为起点，检测是否有套利机会
#include <bits/stdc++.h>
using namespace std;
// 检测是否存在套利机会
bool solve(int n, vector<vector<double>>& G, int s) {
vector<double> d(n + 1, 0); // 存储每个货币的最大兑换值
d[s] = 1.0; // 初始货币的兑换值为 1
bool updated;
for (int k = 0; k < n; ++k) { // 进行 n 次松弛操作
updated = false;
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
// 如果存在从 u 到 v 的汇率，且可以更新 v 的兑换值
if (G[u][v] != 0 && d[u] * G[u][v] > d[v]) {
d[v] = d[u] * G[u][v]; // 更新 v 的兑换值
updated = true;
}
}
}
if (!updated) break; // 如果没有更新，提前退出
}
// 检查是否存在正权环路
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
if (G[u][v] != 0 && d[u] * G[u][v] > d[v]) {
return true; // 存在套利机会
}
}
}
return false; // 不存在套利机会
}
int main() {
int c, n, t = 1; // c: 货币种类数, n: 汇率表行数, t: 测试用例编号
string cu, cv; // 货币名称
double per; // 汇率
map<string, int> currency; // 货币名称到编号的映射
while (cin >> c) { // 读取货币种类数
if (c == 0) break; // 输入结束
int id = 1; // 货币编号从 1 开始
bool flag = false; // 标记是否存在套利机会
currency.clear(); // 清空货币映射
// 读取货币名称并分配编号
for (int i = 0; i < c; i++) {
string cur;
cin >> cur;
currency[cur] = id++;
}
cin >> n; // 读取汇率表行数
// 初始化图的邻接矩阵
vector<vector<double>> G(c + 1, vector<double>(c + 1, 0));
// 读取汇率表并构建图
while (n--) {
cin >> cu >> per >> cv;
int u = currency[cu]; // 源货币编号
int v = currency[cv]; // 目标货币编号
G[u][v] = per; // 存储汇率
}
// 对每个货币作为起点，检测是否存在套利机会
for (int i = 1; i <= c; i++) {
if (solve(c, G, i)) {
flag = true; // 存在套利机会
break;
}
}
// 输出结果
cout << "Case " << t << (flag ? ": Yes" : ": No") << endl;
t++; // 测试用例编号递增
}
return 0;
}1062. 旅游规划
每条边需要维护两个信息：边的长度和花费，可以用结构体或者元组tuple<int,int,int>实现
这类题挺重要的，我们第二次机考几乎出了个原题，建议把这个dijkstra函数背下来，大多数题只需要修改边的定义即可
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f // 定义无穷大值
// Dijkstra算法实现
void dijkstra(int start, int end, int n, vector<vector<tuple<int, int, int>>>& G) {
vector<bool> visited(n + 1, false); // 标记节点是否被访问过
int d[n + 1]; // 存储从起点到每个节点的最短距离
int m[n + 1]; // 存储从起点到每个节点的最小花费
// 初始化距离和花费为无穷大
memset(d, INF, sizeof(d));
memset(m, INF, sizeof(m));
// 起点的距离和花费初始化为0
d[start] = 0;
m[start] = 0;
// 优先队列，按距离从小到大排序，存储 (距离, 花费, 节点)
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push(make_tuple(0, 0, start)); // 将起点加入队列
while (!pq.empty()) {
int u = get<2>(pq.top()); // 当前节点
int cost = get<1>(pq.top()); // 当前节点的花费
int w = get<0>(pq.top()); // 当前节点的距离
pq.pop(); // 弹出当前节点
if (visited[u]) { // 如果节点已经访问过，跳过
continue;
}
visited[u] = true; // 标记当前节点为已访问
// 遍历当前节点的所有邻接节点
for (auto& edge : G[u]) {
int v = get<2>(edge); // 邻接节点
int cc = get<1>(edge); // 从 u 到 v 的花费
int ww = get<0>(edge); // 从 u 到 v 的距离
// 如果通过 u 到 v 的距离更短，更新距离和花费
if (d[u] + ww < d[v]) {
d[v] = d[u] + ww;
m[v] = m[u] + cc;
pq.push(make_tuple(d[v], m[v], v)); // 将更新后的节点加入队列
}
// 如果距离相等但花费更小，更新花费
else if (d[u] + ww == d[v] && m[v] > m[u] + cc) {
m[v] = m[u] + cc;
pq.push(make_tuple(d[v], m[v], v)); // 将更新后的节点加入队列
}
}
}
// 输出从起点到终点的最短距离和最小花费
cout << d[end] << " " << m[end] << endl;
}
int main() {
int n, m, s, d; // n: 节点数, m: 边数, s: 起点, d: 终点
cin >> n >> m >> s >> d;
int u, v, len, cost; // u: 起点, v: 终点, len: 距离, cost: 花费
vector<vector<tuple<int, int, int>>> G(n + 1); // 图的邻接表，存储 (距离, 花费, 邻接节点)
// 读取边的信息并构建图
while (m--) {
cin >> u >> v >> len >> cost;
G[u].push_back(make_tuple(len, cost, v)); // 添加 u 到 v 的边
G[v].push_back(make_tuple(len, cost, u)); // 添加 v 到 u 的边（无向图）
}
// 调用 Dijkstra 算法计算从起点到终点的最短距离和最小花费
dijkstra(s, d, n, G);
return 0;
}1063. 任务调度问题
拓扑排序模板题，机考可能会考，也是背模板（tupo函数）即可
#include <bits/stdc++.h>
using namespace std;
int n; // 节点数
vector<vector<int>> G(101); // 图的邻接表，存储每个节点的邻接节点
int ru[103] = {0}; // 存储每个节点的入度
// 拓扑排序函数
void tupo() {
deque<int> q; // 双端队列，用于存储入度为0的节点
int cnt = 0; // 记录已经处理的节点数
// 将所有入度为0的节点加入队列
for (int i = 1; i <= n; i++) {
if (ru[i] == 0) {
q.push_back(i);
}
}
// 拓扑排序过程
while (!q.empty()) {
int u = q.front(); // 取出队首节点
q.pop_front(); // 弹出队首节点
cnt++; // 已处理的节点数加1
// 遍历当前节点的所有邻接节点
for (auto& v : G[u]) {
ru[v]--; // 将邻接节点的入度减1
if (ru[v] == 0) { // 如果邻接节点的入度变为0，加入队列
q.push_back(v);
}
}
}
// 判断是否所有节点都被处理过
if (cnt == n) {
cout << 1 << endl; // 如果所有节点都被处理过，说明图中无环
} else {
cout << 0 << endl; // 否则，说明图中有环
}
}
int main() {
int k, id; // k: 当前节点的邻接节点数, id: 邻接节点的编号
cin >> n; // 输入节点数
// 输入每个节点的邻接节点
for (int i = 0; i < n; i++) {
cin >> k; // 输入当前节点的邻接节点数
for (int j = 0; j < k; j++) {
cin >> id; // 输入邻接节点的编号
G[i + 1].push_back(id); // 将邻接节点加入当前节点的邻接表
ru[id] += 1; // 邻接节点的入度加1
}
}
// 调用拓扑排序函数
tupo();
return 0;
}