最短路算法——SPFA

用途：

单源最短路径，不可以处理含负权边的图但可以用来判断是否存在负权回路；

复杂度O(kE) 【k <= 2, E 为边数】；

算法核心：

Bellman-Ford 算法的优化，实质与前算法一样，但优化的关键之处在于：只有那些前面被松弛过的点才有可能去松弛它们的邻接点。

模板（已优化）：

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN = 1e3 + 20;

struct edge
{
    int t, nxt, cost;
};

edge e[MAXN*MAXN];
int head[MAXN], cnt;
int dis[MAXN];
bool vis[MAXN];
int N, M;

void init()
{
    memset(head, -1, sizeof(head));
    memset(e, 0, sizeof(e));
    memset(vis, false, sizeof(vis));
    fill(dis, dis+N+1, INF);
    cnt = 0;
}

void add(int from, int to, int weight)
{
    e[cnt].t = to, e[cnt].cost = weight, e[cnt].nxt = head[from], head[from] = cnt++;
}

void debug()
{
    for(int i = 1; i <= N; i++)
    {
        printf("%d ", i);
        for(int k = head[i]; k != -1; k = e[k].nxt)
            printf(" -> %d ", e[k].t);
        puts("");
    }
    puts("");
}

void SPFA(int s)
{
    deque<int> que;
    que.push_back(s);
    dis[s] = 0;
    vis[s] = true;

    while(!que.empty())
    {
        int u = que.front(); que.pop_front();
        vis[u] = false;

        for(int i = head[u]; i != -1; i = e[i].nxt)
        {
            int v = e[i].t;
            if(dis[v] > dis[u] + e[i].cost)
            {
                dis[v] = dis[u] + e[i].cost;
                if(!vis[v])
                {
                    vis[v] = true;
                    if(!que.empty() && dis[v] < dis[que.front()])
                        que.push_front(v);
                    else
                        que.push_back(v);
                }
            }
        }
    }
}

int main()
{
    int a, b, c;
    while(~scanf("%d%d", &M, &N)){
    init();
    while(M--)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    ///debug();

    SPFA(1);

    printf("%d
", dis[N]);
    }
    return 0;
}