Description
N 个城市, 标号从 0 到 N-1,M 条道路, 第 K 条道路 (K 从 0 开始) 的长度为 2^K, 求编号为 0 的城市到其他城市的最短距离.
Input
第一行两个正整数 N(2<=N<=100)M(M<=500), 表示有 N 个城市, M 条道路,
接下来 M 行两个整数, 表示相连的两个城市的编号.
Output
N-1 行, 表示 0 号城市到其他城市的最短路, 如果无法到达, 输出 - 1, 数值太大的以 MOD 100000 的结果输出.
- Sample Input
- 4 3 0 1 1 2 2 0
- Sample Output
- 1 3 -1
参考链接: 1956 Problem C 最短路径
最终 AC 代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX=105, INF=-1;
- int father[MAX], d[MAX][MAX];
- int findFather(int x){ // 找父节点
- if(x == father[x]) return x;
- else return findFather(father[x]);
- }
- int quickMi(int a, int k, int mod){
- int ans = 1;
- long long int res = a;
- while(k){
- if(k & 1) ans = (ans * res) % mod;
- res = (res * res) % mod; // 这里不要写成 res = (res * a) % mod;
- k>>= 1;
- }
- return ans;
- }
- int main(){
- int i, j, k, u, v, x, y, n, m, dis;
- while(scanf("%d %d", &n, &m) != EOF){
- fill(d[0], d[0]+MAX*MAX, INF); // 初始化距离数组
- for(i=0; i<n; i++){
- father[i] = i; // 初始化并查集
- d[i][i] = 0; // 初始化距离数组对角线 这里忘记 答案一定错
- }
- for(k=0; k<m; k++){
- scanf("%d %d", &u, &v);
- x = findFather(u);
- y = findFather(v);
- if(x != y){ // 说明 u,v 未连通
- dis = quickMi(2, k, 100000); // 由于指数太大 采用快速幂
- for(i=0; i<n; i++){
- if(x == findFather(i)){ // 找到以 x 为根节点的集合上所有点
- for(j=0; j<n; j++){
- if(y == findFather(j)){ // 找到以 y 为根节点的集合上所有点
- d[i][j] = d[j][i] = (d[i][u] + dis + d[v][j]) % 100000; // 更新
- }
- }
- }
- }
- father[y] = x; // 合并这两个集合
- }
- }
- for(j=1; j<n; j++) printf("%d\n", d[0][j]);
- }
- return 0;
- }
总结: 这题的关键麻烦就是指数可能会很大, 于是不能用一半的求最短路的方式求解. 然后, 由求快速幂取模的方式, 可以解决指数幂次很大的情况. 于是存储取余后的路径后, 再尝试用 Dijkstra 等求最短路径, 结果依然是 WA. 后来, 参考别人的博客时, 发现别人采用快速幂 + 并查集的方式很简便的解决了, 主要思想是: 如果两个点已经在一个集合中了, 由于后面输入的边是递增的, 所以不用再更新; 如果两个点在两个不同集合上, 那么说明这两个集合没有边连接, 那么更新路径数组, 再合并集合.
来源: http://www.bubuko.com/infodetail-3492763.html