最短路径

[编程题]最短路径

热度指数：19642 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入

输出

8
9
11

算法知识视频讲解

牛客729154675号

呜呜呜有没有大佬帮忙看下我这哪里有问题呀
思路是这样的：

先构建一个二维矩阵，记录点与点的距离。如大佬们所述，不同点间的距离一旦写入，就肯定是两点间的最短距离了，因为后续输入的任何新路，都比前路加起来还要长。因此该矩阵已经可以看作最短路径矩阵了。初始化为除对角线为0外全为-1。

设想这么一种情况：有两个集合A,B，集合内每个点距离其他点的距离都已经是最短路径了，但两个集合之间尚未联通。此时，输入一条新路，连接了A，B中的a,b两点。那此时，就可以把a,b分别看作A,B两棵树的根节点，更新矩阵可以分为三步走：

1.连接两个根节点a,b，将a,b的距离dist[a][b]从-1改为新路的距离

2.从i=0到i=N-1遍历，看哪个点只连了a,b中的一个点，那这个i点就是A或B树的叶子结点，将叶子结点与另一棵树的根节点连接并更新距离，同时分别记录在队列A或队列B中

3.双重遍历队列A、B，相当于将A、B的叶子结点之间互相连接。
这样，AB两个集合就合并为了一个集合，且每个点之间的最短距离都已被更新

下面是代码

#include <stdio.h>
#include <stdlib.h>
#define mod 100000

// 输入一条新路a<=>b后，会存在三层连接的发生：
// 1.两个根结点a, b之间的连接
// 2.两个根节点与另一方的下属结点之间的连接
// 3.下属结点之间的连接

void init_dist(int N, int dist[N][N]){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            dist[i][j] = i==j ?  0 :  -1;
        }
    }
}

void link_node(int N, int from, int to, int dist[N][N], int now_dis){
    dist[from][to] = now_dis;
    dist[to][from] = now_dis;
}

void renew_dist(int N, int from, int to, int dist[N][N], int now_dis){
    // 第一步
    link_node(N, from, to, dist, now_dis);

    // 第二步
    int waitlist[2][N], length0=0, length1=0;
    for(int i=0; i<N; i++){
        if(from !=i && dist[from][i] != -1){            //i是from下属结点，让to和i连接，并让i入(from队)
            link_node(N, i, to, dist, (dist[from][i] + now_dis) % mod);
            waitlist[0][length0] = i;
            length0++;
        }else if(to!=i && dist[to][i] != -1){           //i是to的下属结点，让from和i连接，并让i入(to队)
            link_node(N, i, from, dist, (dist[to][i] + now_dis) % mod);
            waitlist[1][length1] = i;
            length1++;
        }
    }

    // 第三步
    int a, b;   //美观起见
    for(int i=0; i<length0; i++){
        a = waitlist[0][i];
        for(int j=0; j<length1; j++){
            b = waitlist[1][j];
            link_node(N, a, b, dist, (dist[a][from] + dist[from][b]) % mod);
        }
    }
}

int main() {
    int N, M;
    int from, to;
    while (scanf("%d %d", &N, &M) != EOF) {
        int now_dis = 1;
        int dist[N][N];
        init_dist(N, dist);
        for(int i=0; i<M; i++){
            scanf("%d %d", &from, &to);
            if(dist[from][to] == -1){
                renew_dist(N, from, to, dist, now_dis);
            }
            now_dis = (now_dis*2) % mod;
        }
        for(int i=1; i<N; i++){
            printf("%d\n", dist[0][i]);
        }
    }
    return 0;
}

编辑于 2024-02-23 13:14:09 回复(0)