题目描述
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 的结果输出。
样例输入
复制代码
1
2
3
44 3 0 1 1 2 2 0
样例输出
复制代码
1
2
31 3 -1
//用Dijkstra会因为路径取模后大小变化出错
//因为2^k永远大于1+2^1+······+2^(k-1),必须保证下一个路径比前面所有路径加起来都大
//故方法只能用①大整数运算+Dijkstra
//或②并查集建立最小生成树,若后来路径在此树中,直接跳过(如下所示)
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include<iostream> #include<vector> #include<algorithm> using namespace std; const int INF = INT32_MAX; const int MOD = 100000; struct Node { int v, w; Node(int a, int b) :v(a), w(b) {}; }; vector<Node> G[110]; int n, m, d[110], f[110];//d-最短距离 f-并查集 bool vis[110] = { false }; int mod(int a, int b) { int num = 1; while (b--) num = (num * a) % MOD; return num; } int Find(int x) { if (f[x] == x) return x; else return Find(f[x]); } void Dijkstra() { fill(d, d + 110, INF); fill(vis, vis + 110, false); d[0] = 0; for (int i = 0; i < n; i++) { int u = -1, MIN = INF; for (int j = 0; j < n; j++) { if (!vis[j] && d[j] < MIN) { u = j; MIN = d[j]; } } if (u == -1) return; vis[u] = true; for (int j = 0; j < G[u].size(); j++) { int v = G[u][j].v; if (!vis[v] && d[u] + G[u][j].w < d[v]) { d[v] = d[u] + G[u][j].w; } } } } int main() { while (cin >> n >> m) {//注意:多组测试数据 for (int i = 0; i < 110; i++) { G[i].clear(); f[i] = i; } for (int k = 0; k < m; k++) { int u, v; cin >> u >> v; int Fu = Find(f[u]), Fv = Find(f[v]); if (Fu!=Fv) f[Fu] = Fv; else continue; G[u].push_back(Node(v, mod(2, k))); G[v].push_back(Node(u, mod(2, k))); } Dijkstra(); for (int i = 1; i < n; i++) { if (d[i] == INF) cout << -1 << endl; else cout << d[i] % MOD << endl; } } return 0; }
最后
以上就是坦率胡萝卜最近收集整理的关于Codeup最短路径:最短路径的全部内容,更多相关Codeup最短路径内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复