题解 | #最短路径#

#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
const int N = 110, M = 510, MOD = 100000, INF = 0x3f3f3f3f;
int n, m, a, b;
bool vis[N];
ll dist[N];
map<int, int> h, p;

struct Edge {
	int to;
	ll weight;
};
vector<Edge>g[N];

ll qmi(int a, int k, int mod) {
	ll res = 1;
	while (k) {
		if (k & 1) res = res * a % mod;
		k >>= 1;
		a = (ll)a * a % mod;
	}
	return res;
}

int Find(int x) {
	if (p.find(x) == p.end()) p[x] = x, h[x] = 0;
	if (x != p[x]) p[x] = Find(p[x]);
	return p[x];
}

void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (h[x] < h[y]) p[x] = y;
	else if (h[y] < h[x]) p[y] = x;
	else p[y] = x, h[x]++;
}

void dijkstra() {
	fill(dist, dist + N, INF);
	fill(vis, vis + N, false);
	priority_queue<PII, vector<PII>, greater<PII> >heap;
	heap.push({0, 0});
	dist[0] = 0;
	while (!heap.empty()) {// 堆优化版的dijkstra
		PII tmp = heap.top();// 选出距离最小的元素
		heap.pop();
		int elem = tmp.second, dis = tmp.first;
		if (vis[elem]) continue;// 如果已经使用过, 就尝试下一个
		vis[elem] = true;
		for (int i = 0; i < g[elem].size(); i++) {// 遍历所有边
			int t = g[elem][i].to;
			int w = g[elem][i].weight;
			if (dist[t] > dis + w) {
				dist[t] = dis + w;
				heap.push({dist[t], t});
			}
		}
	}
}

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) g[i].clear();// 初始化图
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		if (Find(a) != Find(b)) {
			ll len =  qmi(2, i, MOD);
			Union(a, b);
			g[a].push_back({b, len});
			g[b].push_back({a, len});
		}
	}
	dijkstra();
	for (int i = 1; i < n; i++) {
		if (dist[i] == INF) printf("-1\n");
		else printf("%lld\n", dist[i] % MOD);
	}
	return 0;
}