原题链接（可自行调试）

最短路径2

题目描述:

$N$个城市，标号从$0$到$N-1$，$M$条道路，第$K$条道路（$K$从0开始）的长度为$2^K$，求编号为0的城市到其他城市的最短距离。

输入格式:

多组输入
每组输入第一行两个正整数N$$（2<=N<=100）,M(M<=500),表示有$N$个城市，$M$条道路，
接下来$M$行两个整数，表示相连的两个城市的编号。

输出格式:

$N-1$行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD $100000$ 的结果输出。

样例输入:

4 3
0 1
1 2
2 0

样例输出:

1
3
-1

时间限制: 1000ms
空间限制: 32MB

我的一些想法及我的0分代码

由于$2$的500次方存不下，所以迪杰斯求最短路时只存$k$,最后再求和

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1001
#define mod 100000
int n, m, d[N], p[N], e[101][101];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
bool vis[N], is_e[101][101];
void dfs(int x) {
	if (x == 1) return;
	for (int i = 1; i <= n; i++) {
		if (d[x] == d[i] + e[i][x]) {
			is_e[i][x] = is_e[x][i] = 1;
			dfs(i);
			return;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	p[0] = 1;
	for (int i = 1; i <= 500; i++) p[i] = p[i - 1] * 2 % mod;
	while (cin >> n >> m) {
		for (int i = 1; i <= n; i++) {
			d[i] = 0x3f3f3f3f3f3f3f3f;
			vis[i] = 0;
			for (int j = 1; j <= n; j++) {
				e[i][j] = 0x3f3f3f3f3f3f3f3f;
				is_e[i][j] = 0;
			}
		}
		for (int i = 1; i <= m; i++) {
			int x, y, z = i;
			cin >> x >> y;
			e[x + 1][y + 1] = e[y + 1][x + 1] = min(z - 1, e[x + 1][y + 1]);
		}
		d[1] = 0;
		q.push({0, 1});
		while (!q.empty()) {
			int u = q.top().second;
			q.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (int i = 1; i <= n; i++) {
				int v = i, w = e[u][v];
				if (d[v] >= d[u] + w) {
					d[v] = d[u] + w;
					q.push({d[v], v});
				}
			}
		}
		for (int i = 2; i <= n; i++) {
			if (d[i] == 0x3f3f3f3f3f3f3f3f) {
				cout << "-1\n";
				continue;
			}
			memset(is_e, 0, sizeof is_e);
			dfs(i);
			int ans = 0;
			for (int j = 1; j <= n; j++) {
				for (int k = j + 1; k <= n; k++) {
					if (is_e[j][k]) ans = (p[e[j][k]] + ans) % mod;
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
}