Codeup最短路径：最短路径

题目描述

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

//用Dijkstra会因为路径取模后大小变化出错
//因为2^k永远大于1+2^1+······+2^(k-1)，必须保证下一个路径比前面所有路径加起来都大
//故方法只能用①大整数运算+Dijkstra
//或②并查集建立最小生成树，若后来路径在此树中，直接跳过(如下所示) 

#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最短路径：最短路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。