题解 | 最短路径

#include<iostream>
#include<bitset>
#include<assert.h>

using namespace std;

int Graph[100][100] = {0}; // 记录路径长度，第K条路长为2^K
bitset<512> dis[100] = { 0 }; // 记录每个节点到源点的距离
bool fin[100];
int N, M;

int dismod[100] = {0}; // 到原点距离 mod 100000后的长度
int mod[512]; // 2^K mod 100000后的长度

bool lessthan(bitset<512>& disa, bitset<512>& disb) // 比较两条路径的长度，必然不同
{
	for (int i = M + 1; i >= 1; i--) { // 为了与最大距离比较，多比较一位
		if (disa[i] < disb[i]) {
			return true;
		}
		else if (disa[i] > disb[i]) {
			return false;
		}
	}
	return false;
}

void dijkstra()
{
	int cur = 0;
	bool flag = true;
	while (flag) {
		flag = false;
		fin[cur] = true;
		bitset<512> MinDis;
		MinDis.set();//先设置为最大值

		for (int i = 1; i < N; i++) { // 遍历cur节点的全部边
			if (!fin[i]) { // 连通结点并且还没有处理完
				if (Graph[cur][i] != 0) {
					dis[cur].set(Graph[cur][i]); // 更新i号结点连通到源点的距离
					if (lessthan(dis[cur], dis[i])) {// 从cur出发到i更短
						for (int j = 1; j <= M; j++) { // 更新距离
							dis[i][j] = dis[cur][j];
						}
					}
					dis[cur].reset(Graph[cur][i]); // 恢复dis[cur]
				}
			}
		}

		for (int i = 1; i < N; i++) {
			//求新的最小值和遍历cur邻接点两个不能写到一起去，看上去节省时间，实际上cur中途被修改了
			if (!fin[i] && lessthan(dis[i], MinDis)) {
				flag = true; // 还需继续处理
				cur = i;
				for (int j = 1; j <= M + 1; j++) { // 更新距离
					MinDis[j] = dis[i][j];
				}
			}
		}
	}
}

#define Mod 100000
int main()
{
	cin >> N >> M;
	for (int i = 1; i < N; i++) {
		fin[i] = false;
		for (int j = 1; j <= M + 1; j++) {
			dis[i][j] = 1;
		} // 距离初始化为最大
	}

	mod[1] = 1;// 图中用0表示不连通，所以mod[i]值为2^(i-1)
	for (int i = 2; i <= M; i++) {// 对长度为2^k的路径求mod100000
		mod[i] = (2 * mod[i - 1]) % Mod;
	}

	for (int i = 1; i <= M; i++) {
		int a, b;// 边的两个节点
		cin >> a >> b;
		if (Graph[a][b] != 0) { // 有重复边情况
			continue;
		}
		Graph[a][b] = i;
		Graph[b][a] = i;// 设置边长度，代表2^(i-1)
	}

	// bitset<512> initdis = { 0 };
	dijkstra();
	for (int i = 1; i < N; i++) {
		if (!fin[i]) { // 如果不连通
			cout << -1 << endl;
			continue;
		}
		for (int j = 1; j <= M; j++) {
			if (dis[i][j] == 1) {
				dismod[i] += mod[j];
			}
		}
		dismod[i] %= Mod;
		cout << dismod[i] << endl;
	}

	return 0;
}

这道题有两种思路。一是基础思路，dijkstra算法，难点在于路径长度比较不能用常规的长整数类型，因为路径长度超出表示范围。

这里使用位图表示，第i位为1就表示包含一条长度为2^(i-1)的路径，用0表示两城市不连接。还要注意dijkstra算法使用本轮选择节点更新其他结点到源点距离的过程与选择下一轮节点的过程不能写在一起，这里写错了导致一直不通过。

二是更小生成树的思路。首先考察边长的规律，第K条道路（K从0开始）的长度为2^K，因此第k条路径比前面所有路径加起来都大。能用前面的边连通，就不应该用后续的边。接下来我们证明最小生成树中源点a到任意节点b距离最短：最小生成树中a与b必然是联通的，由于前述性质，再往后的边不必考虑了。而前面这些边，假如存在一条更短的到b的路径，则与最小生成树中的a到b路径形成一个环路，此时可以去掉最小生成树中的a到b路径的至少一条边，形成一个成本更低的树，这与最小生成树性质不符。于是使用kruskal构造最小生成树既可，使用并查集判断一条边的两节点是否已连通，然后对树做一次遍历就得到最短路径。