最短路 SPFA

国人发明出来的一种计算单源最短路的方法，算是BF算法的一种简化版本，代码量较小，时间复杂度无法证明。因为代码量较小，速度又不错，经常与其他算法组合出现，可以用来判断负环。

模板代码：

struct edge{
    int from, to, cost;
    edge() {}
    edge(int _from, int _to, int _cost) {
        from = _from;
        to = _to;
        cost = _cost;
    }
};

vector<int>G[maxv];
vector<edge> edges;
int rank[maxv], dis[maxv];
bool inque[maxv];

void add(int u, int v, int w) {
    edges.push_back(edge(u, v, w));
    int m = edges.size();
    G[u].push_back(m-1);
}

int spfa(int s, int n) {
    for (int i = 0; i <= n; i++) {
        dis[i] = INF;
        rank[i] = 0;
        inque[i] = false;
    }
    dis[s] = 0;
    rank[s] = 1;
    inque[s] = true;
    queue<int>que;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();
        inque[u] = false;
        que.pop();
        for (int i = 0; i < (int)G[u].size(); i++) {
            edge e = edges[G[u][i]];
            if (dis[e.to] > dis[u] + e.cost) {
                dis[e.to] = dis[u] + e.cost;
                if (!inque[e.to]) {
                    que.push(e.to);
                    inque[e.to] = true;
                    rank[e.to]++;
                    if (rank[e.to] >= n) return false;
                }
            }
        }
    }
    return true;
}

POJ 3259 Wormholes

有两种路，一种走完这条路需要的时间是正的，另一种需要的时间是负的，问有没有这样一条回路，走完整条回路后，需要的时间的和是负的(判负环)

判断每个点的入队次数，如果大于N（图中总的点数），就是有负环

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int maxv = 1000;
const int INF = 1000000000;

struct edge{
    int from, to, cost;
    edge() {}
    edge(int _from, int _to, int _cost) {
        from = _from;
        to = _to;
        cost = _cost;
    }
};

vector<int>G[maxv];
vector<edge> edges;
int rank[maxv], dis[maxv];
bool inque[maxv];

void add(int u, int v, int w) {
    edges.push_back(edge(u, v, w));
    int m = edges.size();
    G[u].push_back(m-1);
}

int spfa(int s, int n) {
    for (int i = 0; i <= n; i++) {
        dis[i] = INF;
        rank[i] = 0;
        inque[i] = false;
    }
    dis[s] = 0;
    rank[s] = 1;
    inque[s] = true;
    queue<int>que;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();
        inque[u] = false;
        que.pop();
        for (int i = 0; i < (int)G[u].size(); i++) {
            edge e = edges[G[u][i]];
            if (dis[e.to] > dis[u] + e.cost) {
                dis[e.to] = dis[u] + e.cost;
                if (!inque[e.to]) {
                    que.push(e.to);
                    inque[e.to] = true;
                    rank[e.to]++;
                    if (rank[e.to] >= n) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    //freopen("in.txt", "r", stdin);
    int t, n, m, W, u, v, w;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &W);
        for (int i = 0; i <= n; i++) G[i].clear();
        edges.clear();
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }
        for (int i = 0; i < W; i++) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, -w);
        }
        for (int i = 1; i <= n; i++) {
            add(n+1, i, 0);
        }
        if (spfa(n+1, n+1)) {
            puts("NO");
        } else {
            puts("YES");
        }
    }
    return 0;
}

HDU 4460 Friend Chains

求一个无向图中的最长的最短路
枚举以每个点为起点的最短路，维护最大值(就是个暴力)

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 1000 + 5;
const double INF = 1000000000;

struct edge{
    int from, to, cost;
    edge() {}
    edge(int _from, int _to, int _cost) {
        from = _from;
        to = _to;
        cost = _cost;
    }
};

vector<int>G[maxn];
vector<edge> edges;
bool inque[maxn];
int dis[maxn];

void add(int u, int v, int w) {
    edges.push_back(edge(u, v, w));
    int m = edges.size();
    G[u].push_back(m-1);
}

int spfa(int n, int s) {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    dis[s] = 0;
    inque[s] = true;
    queue<int>que;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();
        inque[u] = false;
        que.pop();
        for (int i = 0; i < (int)G[u].size(); i++) {
            edge e = edges[G[u][i]];
            if (dis[e.to] > dis[u] + e.cost) {
                dis[e.to] = dis[u] + e.cost;
                if (!inque[e.to]) {
                    que.push(e.to);
                    inque[e.to] = true;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dis[i]);
    return ans;
}

map<string, int> mp;

void init(int n) {
    for (int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
    mp.clear();
}

int main() {
    //freopen("in.txt", "r", stdin);
    int n, m;
    while (scanf("%d", &n) != EOF && n) {
        init(n);
        int cnt = 1;
        char a[20], b[20];
        for (int i = 0; i < n; i++) {
            scanf("%s", a);
            if (mp[a] == 0) mp[a] = cnt++;
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%s%s", a, b);
            int u = mp[a], v = mp[b];
            add(u, v, 1);
            add(v, u, 1);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, spfa(n, i));
        }
        printf("%d\n", ans == INF ? -1 : ans);
    }
    return 0;
}