G9 - ShortestPath-Dijkstra

c++11 graph algorithm limits unordered_set

template< class type >
class SPD_Dijkstra {
	const int n;
	unordered_set<int> vis;	// 表示还没有(确定原点到该点的最短路且已经完成松弛操作)的集合.最后被动确定的点不被删除
public:
	type INF = numeric_limits<type>::max()>>1u;
	type dis[maxn+1] {};	// 表示源点到该点的最短路径长度
	type ar[maxn+1][maxn+1] {};	// 使用邻接矩阵存储图的结构
	explicit SPD_Dijkstra(const int n): n(n) {	// single point shortest path for dense graph (Dijkstra)
		for (int i = 1; i <= n; i++) fill(ar[i]+1, ar[i]+n+1, INF);
		for (int i = 1; i <= n; i++) ar[i][i]= 0;
	}
	void solve(const int source) {
		for (int i = 1; i <= n; i++) vis.insert(i);
		fill(dis+1, dis+n+1, INF);
		dis[source] = 0;	// 此时虽然源点到源点的最短路为0,但还没有更新其出边,所以不能将源点从vis中删除
		for (int k = 1, cur; k < n; k++) {	// 确定源点到vis中最短距离的点->更新其出边->从vis中删除该点,最后一个点被动确定
			cur = *vis.begin();	// 在vis中寻找距离源点最近的点
			for (const auto i : vis) if (dis[i] < dis[cur]) cur = i;
			vis.erase(cur);
			for (const auto i : vis) dis[i] = min(dis[i], dis[cur] + ar[cur][i]);	// 尝试松弛其出边
		}
	}
};

单源汇

template< class type >
class SP {
	const type INF = numeric_limits< type >::max() >> 1u;
	const int n;
	unordered_set< int > vis;
	type dis[maxn + 1];
public:
	int ar[maxn + 1][maxn + 1] {};
	explicit SP(const int n): n(n) {
		for (int i = 1; i <= n; i++) {
			fill(ar[i] + 1, ar[i] + n + 1, INF);
			ar[i][i] = 0;
		}
	}
	int solve(int source, int target) {
		unordered_set< int >().swap(vis);
		for (int i = 1; i <= n; i++) vis.insert(i);
		fill(dis + 1, dis + n + 1, INF);
		dis[source] = 0;
		for (int k = 1, cur; k < n; k++) {
			cur = *vis.begin();
			for (const auto i : vis) if (dis[i] < dis[cur]) cur = i;
			vis.erase(cur);
			if (dis[cur] == INF) return -1;
			if (cur == target) return dis[cur];
			for (const auto i : vis) dis[i] = min(dis[i], dis[cur] + ar[cur][i]);
		}
		return dis[target] == INF ? -1 : dis[target];
	}
};