GGAutomaton's Blog
0%

spfa模板

发表于 分类于 ，

复杂度最坏为\(O(nm)\) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void spfa(int s) {
    queue<int> que;
    memset(inque,false,sizeof(inque));
    for (int i=1;i<=n;i++) dist[i]=1e9;
    que.push(s);dist[s]=0;inque[s]=true;
    while (!que.empty()) {
        int u=que.front();que.pop();
        inque[u]=false;
        for (int e=head[u];e!=-1;e=nxt[e]) {
            int v=vet[e];
            if(dist[v]>dist[u]+cost[e]) {
                dist[v]=dist[u]+cost[e];
                if (!inque[v]) {
                    inque[v]=true;
                    que.push(v);
                }
            }
        }
    }
}