一个实现了排序接口的切片，一个往文件写数据的函数，一个生成随机时间的函数，一个断言
utils.go
gopackage raft
import (
"fmt"
"io"
"math/rand"
"os"
"time"
)
SPFA（Shortest Path Faster Algorithm）算法是一种用于求解单源最短路径问题的图算法。它与Dijkstra算法类似，但更适用于存在负权边的情况。下面详细解释SPFA算法的原理和步骤：
基本原理： SPFA算法是一种广度优先搜索（BFS）的变种，用于寻找从源点到其他所有点的最短路径。它的核心思想是通过松弛操作逐步缩小每个顶点到源点的估计距离，直到找到最短路径或确定没有更短路径。
步骤：
-
初始化：将源点的最短距离初始化为0，其他点的最短距离初始化为无穷大（通常用一个足够大的数表示）。然后将源点入队。
-
进行松弛操作：从队列中取出一个点，遍历其所有邻接点，尝试通过这个点获得更短的路径。如果通过该点可以获得更短的距离，就进行松弛操作。即，如果
dist[u] + weight < dist[v]，其中u为当前点，v为邻接点，dist[u]表示从源点到u的距离，weight表示边(u, v)的权重，那么更新dist[v] = dist[u] + weight。 -
将更新的点入队：如果通过松弛操作更新了某个点
v的最短距离，将v入队，以便继续扩展从v出发的路径。 -
重复步骤2和步骤3，直到队列为空。这个过程类似于BFS，通过不断松弛和入队，最终确定了每个点到源点的最短距离。
-
结果：在算法结束后，
dist[i]存储了源点到顶点i的最短距离。如果dist[i]仍然是初始值（无穷大），表示从源点无法到达顶点i。
注意事项：
- SPFA算法适用于包括负权边的情况，但不适用于存在负权环的图。
- 为了防止无限循环，SPFA算法使用一个队列来存储需要松弛的点。当一个点被加入队列后，可能被多次取出进行松弛操作。但如果一个点被松弛的次数超过了顶点数，那么图中存在负权环。因此，SPFA算法使用一个数组来记录每个点的入队次数，当某点入队次数超过顶点数时，可以判断存在负权环。
SPFA算法在实际应用中非常有用，特别是在求解具有负权边的最短路径问题。
cpp#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MOD = 100003; // 题目要求的模数
int main() {
int N, M;
cin >> N >> M; // 读取顶点数 N 和边数 M
vector<vector<int>> graph(N + 1); // 用邻接表存储图
vector<int> dist(N + 1, -1); // 到达每个顶点的距离，-1 表示尚未访问
vector<int> ways(N + 1, 0); // 从顶点1到各个顶点的最短路的数量
for (int i = 0; i < M; ++i) {
int x, y;
cin >> x >> y;
graph[x].push_back(y); // 无向图，连接两个顶点
graph[y].push_back(x); // 同样需要连接回来
}
queue<int> q; // 使用队列进行BFS
q.push(1); // 从顶点1开始
dist[1] = 0; // 顶点1到达自身的距离为0
ways[1] = 1; // 从顶点1到达自身的最短路数量为1
while (!q.empty()) {
int current = q.front(); // 取出队列中的当前顶点
q.pop();
for (int neighbor : graph[current]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[current] + 1; // 计算到达邻居的距离
ways[neighbor] = ways[current]; // 以当前顶点的最短路数量初始化邻居的数量
q.push(neighbor); // 将邻居加入队列，继续BFS
} else if (dist[neighbor] == dist[current] + 1) {
ways[neighbor] = (ways[neighbor] + ways[current]) % MOD; // 若距离相等，累加最短路数量，注意取模
}
}
}
