帮我写一个spfa算法模板

### 回答1：
好的，这是一份 SPFA 算法模板：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1e5+10;
const int INF=0x3f3f3f3f;
int head[N],tot,n,m,s,dis[N];
bool vis[N];
struct node{
    int next,to,w;
}e[M];
inline void add(int from,int to,int w){
    e[++tot].to=to;
    e[tot].w=w;
    e[tot].next=head[from];
    head[from]=tot;
}
inline void SPFA(int s){
    queue<int> q;
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int to=e[i].to;
            if(dis[to]>dis[u]+e[i].w){
                dis[to]=dis[u]+e[i].w;
                if(!vis[to]){
                    q.push(to);
                    vis[to]=1;
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int from,to,w;
        cin>>from>>to>>w;
        add(from,to,w);
    }
    SPFA(s);
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

请注意，这份代码仅仅是一个模板，需要根据实际需求进行修改。

### 回答2：
SPFA（Shortest Path Faster Algorithm）是一种用于求解最短路径的算法，下面给出一个SPFA算法的模板：

import queue

# 定义图的节点类
class Node:
    def __init__(self, index):
        self.index = index
        self.next = None
        self.weight = None

# SPFA算法函数
def spfa(start, end, graph):
    # 初始化距离数组和队列
    dist = [float('inf')] * len(graph)
    dist[start] = 0
    q = queue.Queue()
    q.put(start)
  
    # 利用队列进行广度优先搜索
    while not q.empty():
        u = q.get()
        node = graph[u]
        while node:
            v = node.index
            w = node.weight
            # 松弛操作
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                q.put(v)
            node = node.next

    # 返回最短路径长度
    return dist[end]

# 测试数据
if __name__ == "__main__":
    # 初始化图的邻接表
    graph = [None] * 5
    graph[0] = Node(1)
    graph[0].next = Node(2)
    graph[0].next.next = Node(4)
    graph[0].weight = 2
    graph[0].next.weight = 4
    graph[0].next.next.weight = 1
    graph[1] = Node(2)
    graph[1].next = Node(3)
    graph[1].weight = 6
    graph[1].next.weight = 3
    graph[2] = Node(3)
    graph[2].weight = 2
    graph[4] = Node(3)
    graph[4].weight = 3

    start = 0
    end = 3
    result = spfa(start, end, graph)
    print("最短路径长度：", result)

该模板中，首先定义了一个节点类表示图的节点，包含节点索引、指向的下一个节点和边的权重信息。

然后，实现了SPFA算法的函数`spfa`，其中利用队列实现广度优先搜索，对于每个节点，根据当前节点的距离更新相邻节点的距离值。

最后，在主函数中，根据测试数据初始化图的邻接表，并设定起点和终点，最后调用`spfa`函数求解最短路径长度并输出结果。

希望对你有帮助！

### 回答3：
SPFA算法，即适用于求解单源最短路径的 Bellman-Ford 算法的一种优化算法，全称为 Shortest Path Faster Algorithm。下面是一个SPFA算法的模板：

import collections

def spfa(graph, start):
    # 初始化距离数组和队列
    distance = [float('inf')] * len(graph)
    distance[start] = 0
    queue = collections.deque([start])
    in_queue = [False] * len(graph)
    in_queue[start] = True

    while queue:
        curr_node = queue.popleft()
        in_queue[curr_node] = False

        for neighbor, weight in graph[curr_node]:
            new_distance = distance[curr_node] + weight
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                if not in_queue[neighbor]:
                    queue.append(neighbor)
                    in_queue[neighbor] = True
    
    return distance

其中，`graph`为表示图的邻接表形式，包含了节点及其邻居节点及边的权重信息。`start`表示起始节点的索引。

算法运行开始时，将起始节点加入队列，并设置距离数组中起始节点的距离为0。进入循环，每次从队列中取出一个节点，并更新其连接节点的最短距离。如果发现某个节点的最短距离有更新，则将该节点加入队列中继续扩展，并将其标记为在队列中。

最后，返回得到的各个节点到起始节点的最短距离数组 `distance`。如果某个节点的最短距离为初始时设置的 `float('inf')`，则表示该节点不可到达。

这是一个简单的SPFA算法模板，适用于解决不含负权环的最短路径问题。需要注意的是，如果图中存在负权环，该算法将无法得到正确结果，因为它没有负权环的停止条件。