This doc has been marked needs-review. Following information are in upcoming update plan.

mooyyu

G10 - ShortestPath-SPFA

c++11 graph functional queue 

template< class type >
class SPFA {
	const int n;
	bool vis[maxn+1] {};	// 表示该点(被松弛成功但还没有松弛其出边)的状态, 也即是否在队列中
	type cnt[maxn+1] {};	// 表示源点到该点的最短路径的边数
	queue<int> que;
public:
	struct node {
		int to, ptr;
		type len;
	} ar[maxm+1];	// 链式前向星存图, ar[0]不存, ptr==0视为ptr==null
	int head[maxn+1] {};
	type INF = numeric_limits<type>::max()>>1u;
	type dis[maxn+1] {};	// 表示源点到该点的最短路径长度
	explicit SPFA(const int n): n(n) {}
	bool solve(const int source) {
		fill(cnt+1, cnt+n+1, 0);	// 如不连通，必须全为0，连通的话只需源点为0
		fill(dis+1, dis+n+1, INF);	// 判断负环，只需保证算法过程不会溢出即可（都为相同的数，减少运算），也统一这么做吧，INF这个值比较好
		fill(vis+1, vis+n+1, true);	// 为了判断负环, 因为有图并不全连通的可能所以需要vis全部标记并放入队列
		queue<int>().swap(que);
		for (int i = 1; i <= n; i++) que.push(i);	// 如果题目保证全连通, 可以只操作源点
		dis[source] = 0;	// 确定源点到源点的最短路,没有更新,所以在vis中标记源点。如只需判断负环，则这一步不需要
		while (!que.empty()) {
			static int cur;
			vis[cur = que.front()] = false, que.pop();
			for (int i = head[cur]; i; i = ar[i].ptr) {	// 尝试松弛其出边
				static type dist;
				if ((dist = dis[cur] + ar[i].len) < dis[ar[i].to]) {
					dis[ar[i].to] = dist;
					if ((cnt[ar[i].to] = cnt[cur] + 1) == n) return false;	// 抽屉原理
					if (!vis[ar[i].to]) que.push(ar[i].to), vis[ar[i].to] = true;
				}
			}
		}
		return true;
	}
};
单源汇 
template< class type >
class SP {
	type dis[maxn + 1] {};
	bool vis[maxn + 1] {};
	const int n;
	queue< int > que;
public:
	const int INF = numeric_limits< type >::max() >> 1u;
	struct {
		int to, ptr;
		type len;
	} ar[maxm + 1] {};
	int head[maxn + 1] {};
	explicit SP(const int n): n(n) {}
	type solve(int source, int target) {
		fill(vis + 1, vis + n + 1, false);
		fill(dis + 1, dis + n + 1, INF);
		queue< int >().swap(que);
		vis[source] = true, dis[source] = 0, que.push(source);
		while (!que.empty()) {
			static int cur;
			cur = que.front(), que.pop(), vis[cur] = false;
			for (int i = head[cur]; i; i = ar[i].ptr)
				if (dis[cur] + ar[i].len < dis[ar[i].to]) {
					dis[ar[i].to] = dis[cur] + ar[i].len;
					if (!vis[ar[i].to]) {
						que.push(ar[i].to);
						vis[ar[i].to] = true;
					}
				}
		}
		return dis[target];
	}
};

拓展应用

判断负环 
template< class type >
class SP {
	const type INF = numeric_limits< type >::max() >> 1u;
	type dis[maxn + 1] {};
	bool vis[maxn + 1] {};
	int cnt[maxn + 1] {};
	const int n;
	queue< int > que;
public:
	struct {
		int to, ptr;
		type len;
	} ar[maxm + 1] {};
	int head[maxn + 1] {};
	explicit SP(const int n): n(n) {}
	bool solve() {
		fill(vis + 1, vis + n + 1, true);
		fill(cnt + 1, cnt + n + 1, 0);
		fill(dis + 1, dis + n + 1, INF);
		queue< int >().swap(que);
		for (int i = 1; i <= n; i++) que.push(i);
		while (!que.empty()) {
			static int cur;
			cur = que.front(), que.pop(), vis[cur] = false;
			for (int i = head[cur]; i; i = ar[i].ptr)
				if (dis[cur] + ar[i].len < dis[ar[i].to]) {
					if ((cnt[ar[i].to] = cnt[cur] + 1) == n) return false;
					dis[ar[i].to] = dis[cur] + ar[i].len;
					if (!vis[ar[i].to]) {
						que.push(ar[i].to);
						vis[ar[i].to] = true;
					}
				}
		}
		return true;
	}
};