SPFA

时间复杂度 $O(VE)$

伪代码

    Queue q
    q.add(s) // s的距离初始为0, 其他顶点的距离初始为Infinity

    while(!q.isEmpty())
        v = q.remove()
        for (w : v.adjs)  // w是v的邻接顶点
            if(dv + d(v, w) < dw)
                dw = dv + d(v, w)
                if(!q.contains(w)) //检查w是否在当前队列中，不在则入队
                    q.add(w)

时间复杂度分析

SPFA算法过程中，顶点一层一层地入队出队，一张图最多有$|V|$层(以$s$为第$1$层)，所以按层计，顶点最多入队$|V|$次。第$1$层顶点个数为$1$，其余每层顶点数不会超过$|V|$（第$8$行所保证）。这里重点解释一下，一个顶点可能会通过不同的路径重复属于某一层，例如 $s>a>c，s>b>c$ ，没有第$8$行检查的话，$c$可以在第$3$层顶点里出现两次。但有了第$8$行，使得一个顶点只能在一层顶点里出现一次，否则算法复杂度将超过$O(|V||E|)$，后面还会讨论这种情况。当第一层有$|V|-1$ 个，其余所有层都有$|V|$个顶点时达到复杂度上限。

除第$1$层外每一层顶点入队引起$|E|$次松弛尝试，除第一层外的其他$|V|-1$层的总时间复杂度为$O((|V|-1)\ast |E|)$。因为第一层(顶点$s$)引起的松弛尝试不会超过$|E|$，所以总的时间复杂度为$O(|V||E|)$。

Acwing 1129.热浪

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！

他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。

农夫 John 此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

John 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 $T$ 个城镇，为了方便标号为 $1$ 到 $T$。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 $C$ 条直接连接 $2$ 个城镇的道路。

每条道路由道路的起点 $R_s$，终点 $R_e$ 和花费 $C_i$ 组成。

求从起始的城镇 $T_s$ 到终点的城镇 $T_e$ 最小的总费用。

输入格式

第一行: $4$ 个由空格隔开的整数: $T,C,T_s,T_e$;

第 $2$ 到第 $C+1$ 行: 第 $i+1$ 行描述第 $i$ 条道路，包含 $3$ 个由空格隔开的整数: $R_s,R_e,C_i$。

输出格式

一个单独的整数表示从 $T_s$ 到 $T_e$ 的最小总费用。

数据保证至少存在一条道路。

数据范围

$1\le T\le 2500$,
$1\le C\le 6200$,
$1\le T_s,T_e,R_s,R_e\le T$,
$1\le C_i\le 1000$

输入样例：

    7 11 5 4
    2 4 2
    1 4 3
    7 2 2
    3 4 3
    5 7 5
    7 3 3
    6 1 1
    6 3 4
    2 4 3
    5 6 3
    7 2 1

输出样例：

    7

思路:

可以看出是单源最短路问题, 选择 SPFA $O(VE)$ 或 朴素dijkstra $O(V^2)$ 或 堆优化dijkstra $O((V+E)\log E)$

代码:

SPFA, 循环队列实现

    ...
    const int N = 2510, M = 6200 *2 + 10;
    int n,m,S,T;
    int h[N], e[M], w[M] ,ne[M], idx;
    int dist[N], q[N];
    bool st[N];

    void add(int a, int b, int c){
        e[idx]= b, w[idx] = c, ne[idx] = h[a] ,h[a] = idx  ++;
    }

    void spfa(){
        memset(dist, 0X3f, sizeof dist);
        dist[S] = 0;
        int hh = 0, tt = 1;
        q[0] = S, st[S] = true;

        while(hh != tt){
            int t = q[hh++];
            if(hh == N) hh=0;
            st[t] = false;

            for(int i=h[t]; ~i; i =ne[i]){
                int j = e[i];
                if(dist[j]>dist[t]+w[i]){
                    dist[j] = dist[t] + w[i];
                    if(!st[j]){
                        q[tt++] = j;
                        if(tt==n) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
    }
    int main(){
        cin>>n>>m>>S>>T;
        memset(h, -1, sizeof h);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c), add(b,a,c);
        }
        spfa();
        cout<<dist[T]<<endl;
        return 0;
    }