多源BFS+思维转换：小镇购物

Bertha 。 2023-10-06 19:38 58阅读 0赞

## 多源BFS+思维转换：小镇购物 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

我们最开始的思路通常为从每个商店开始进行bfs，但该题的商店数达到1e5，从商店开始进行bfs的思路时间复杂度是无法接受的。注意到商品种类最多为100种，这时我们需要进行思维转换，不对商店做bfs，而是对商品做bfs，对每种商品做bfs，更新该种商品到每个商店的最短距离，可用一个二维数组dis\[\] \[\]保存距离，dis\[i\] \[j\]表示从商店i到商品j的最短距离，由于一种商品在多个商店出现，因此是多源bfs。 dis\[\] \[\]既可存最短距离又可作为标记数组（若dis\[i\] \[j\]被更新，则dis\[i\] \[j\]即为商品j到商店i的最短距离，之后不需要再更新该值，此为多源bfs的重要特性。多源bfs保证了每个商店第一次被访问都是从离它最近的拥有某特定商品的商店扩展过来的）。

**需注意的点：**

*  如何存每种商品所对应的商店？注意不需要使用List< Integer >\[\] 保存每种商品对应的商店列表，这样的开销很大。直接使用一个一维数组保存每个商店所拥有的商品类别即可，下标表示商店编号，值为商品编号，在bfs的开始时，只需遍历该一维数组，找到所有拥有特定商品的商店，入队即可。
 *  如何更新距离矩阵dis？注意不需要将商店号和bfs遍历树的层数level一同入队，只需要入队商店号即可。若当前出队商店为now，当前遍历到的商店为next，当前bfs对应的商品为good，则更新good到next的距离即为：`distance[next][good] = distance[now][good] + 1`
 *  如何获得输出结果？注意需要输出的答案是所经过所有路径权值的和，而不是到不同商店路径的最小值，且每个商店本身拥有的商品也算一种购买的商品。设商店号为i，将dis\[i\]的前k个元素按升序排序，该商店购买s种商品的最小代价即为dis\[i\]排序后前s个元素的累加和

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static final int MMAX = 100002;
        static int[][] distance = new int[MMAX][102];
        static List<Integer> list = new ArrayList<>();
        static List<Integer>[] adject = new List[MMAX];
        static int[] goods = new int[MMAX];
        static LinkedList<Integer> q = new LinkedList<>();
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n, m, k, s, i, j, from, to, gNum, ans;
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                m = scanner.nextInt();
                k = scanner.nextInt();
                s = scanner.nextInt();
                for (i = 0;i <= n;i++) {
        
                    adject[i] = new ArrayList<>();
                    Arrays.fill(distance[i], -1);
                }
                for (i = 1;i <= n;i++) {
        
                    gNum = scanner.nextInt();
                    goods[i] = gNum;
                    distance[i][gNum] = 0;
                }
                for (i = 0;i < m;i++) {
        
                    from = scanner.nextInt();
                    to = scanner.nextInt();
                    adject[from].add(to);
                    adject[to].add(from);
                }
                for (i = 1;i <= k;i++) {
        
                    bfs(i, n);
                }
                for (i = 1;i <= n;i++) {
        
                    list.clear();
                    ans = 0;
                    for (j = 1;j <= k;j++) {
        
                        list.add(distance[i][j]);
                    }
                    Collections.sort(list);
                    for (j = 0;j < s;j++) {
        
                        ans += list.get(j);
                    }
                    System.out.print(ans + " ");
                }
                System.out.print('\n');
            }
    
        }
    
        static void bfs(int good, int n) {
        
            int i, next, j;
            int now;
            for (j = 1;j <= n;j++) {
        
                if (goods[j] == good) {
        
                    q.add(j);
                }
            }
            while (!q.isEmpty()) {
        
                now = q.pop();
                for (i = 0;i < adject[now].size();i++) {
        
                    next = adject[now].get(i);
                    if (distance[next][good] != -1) {
        
                        continue;
                    }
                    distance[next][good] = distance[now][good] + 1;
                    q.add(next);
                }
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/82bdba8c331b400c8e4157c645275e85.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/3f98454652d04336bce4d06340e2d341.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/73d85dbbabbb4bf0a32fe6eb740d32ef.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16