写一个简单的SPFA模板
时间: 2024-05-01 10:19:24 浏览: 11
好的,以下是一个简单的SPFA模板:
```
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector<pair<int, int>> g[MAXN]; // 存储有向图,pair 中第一个数表示终点,第二个数表示边权
int dist[MAXN]; // 存储源点到每个点的最短距离
bool in_queue[MAXN]; // 标记每个点是否在队列中
void spfa(int s) { // s 表示源点编号
memset(dist, INF, sizeof(dist)); // 初始化 dist 数组为 INF,表示距离无限远
memset(in_queue, 0, sizeof(in_queue)); // 初始化 in_queue 数组为 false,表示所有点都不在队列中
queue<int> q;
q.push(s);
dist[s] = 0;
in_queue[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop(); // 取出队首元素
in_queue[u] = false; // 标记 u 不在队列中
for (auto v : g[u]) { // 枚举 u 的出边
if (dist[v.first] > dist[u] + v.second) { // 更新 dist[v]
dist[v.first] = dist[u] + v.second;
if (!in_queue[v.first]) { // 如果 v 不在队列中,则将 v 加入队列
q.push(v.first);
in_queue[v.first] = true;
}
}
}
}
}
```
解释一下每个部分的作用:
1. 常量 INF 表示距离无限远,MAXN 表示最大点数。
2. g 数组存储有向图,pair 中第一个数表示终点,第二个数表示边权。
3. dist 数组存储源点到每个点的最短距离。
4. in_queue 数组标记每个点是否在队列中。
5. spfa 函数实现 SPFA 算法,s 表示源点编号。
6. 首先将 dist 数组初始化为 INF,表示距离无限远;将 in_queue 数组初始化为 false,表示所有点都不在队列中;将源点 s 加入队列并标记在队列中,并将 dist[s] 初始化为 0。
7. 进行队列操作:取出队首元素 u,枚举 u 的出边,如果可以通过 u 更新 dist[v] 的值,则更新 dist[v] 并将 v 加入队列。当队列为空时,SPFA 算法结束。