G8 - ShortestPath-BellmanFord

c++11 graph cstring functional

template< class type >
class SP_Bellman_Ford {
	const int n, m;
public:
	struct node {
		int from, to;
		type len;
	} ar[maxm];
	type INF = numeric_limits<type>::max()>>1u;
	type dis[maxn+1], bak[maxn+1];
	explicit SP_Bellman_Ford(const int n, const int m) : n(n), m(m) {}
	void solve(const int source, const int k) {
		fill(dis + 1, dis + n + 1, INF);
		dis[source] = 0;
		for (int idx = 0; idx < k; idx++) {
			copy(dis+1, dis+n+1, bak+1);
			for (int i = 0; i < m; i++)
				if (bak[ar[i].from] != INF)
					dis[ar[i].to] = min(dis[ar[i].to], bak[ar[i].from] + ar[i].len);
		}
	}
};

单源汇

template< class type >
class SP {
	type dis[maxn + 1] {};
	type bak[maxn + 1] {};
	const int n, m;
public:
	const type INF = numeric_limits< type >::max() >> 1u;
	struct {
		int e, u;
		type len;
	} ar[maxm];
	explicit SP(const int n, const int m): n(n), m(m) {}
	type solve(int source, int target, int k) {
		fill(dis + 1, dis + n + 1, INF);
		dis[source] = 0;
		while (k--) {
			copy(dis + 1, dis + n + 1, bak + 1);
			for (int i = 0; i < m; i++)
				if (bak[ar[i].e] != INF)
					dis[ar[i].u] = min(dis[ar[i].u], bak[ar[i].e] + ar[i].len);
		}
		return dis[target];
	}
};