多重图问题？

[题目链接](https://www.nowcoder.com/practice/f95ed44fef0d40f8b82a1d5a2f8dca93)

思路

给定一张无向连通多重图（可能含自环和重边），小淘、小天、阿牛三人分别位于不同节点，图中还有一个宝藏节点。求三人到宝藏的最短路中，最小值和最大值。

关键观察

1. 图中所有边权均为 1（题目要求经过的边数），因此最短路用 BFS 求解即可。
2. 只需从宝藏节点出发做一次 BFS，得到宝藏到所有节点的最短距离，然后直接读取三人所在节点的距离值。
3. 自环对最短路没有影响（走自环不会缩短到任何节点的距离），构建邻接表时跳过自环即可。
4. 重边在无权图 BFS 中不影响结果，无需特殊处理（重边不会产生更短的路径）。

算法步骤

1. 读入 （点数）、（边数）。
2. 读入小淘、小天、阿牛、宝藏的节点编号 。
3. 建邻接表，跳过自环（ 的边）。
4. 从 出发做 BFS，记录每个节点到 的最短距离。
5. 输出 和 。

样例演示

示例 1：，小淘在 4，小天在 5，阿牛在 3，宝藏在 2。

从节点 2 出发 BFS：

• 
• （与 2 直接相邻）
• （经过节点 1）

三人距离：，最小值为 1，最大值为 2，输出 1 2。

复杂度

• 时间复杂度：，BFS 遍历所有节点和边各一次。
• 空间复杂度：，邻接表和距离数组。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int a, b, c, t;
    cin >> a >> b >> c >> t;

    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (u != v) { // 跳过自环
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    // 从宝藏节点 t 出发做 BFS
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[t] = 0;
    q.push(t);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    int da = dist[a], db = dist[b], dc = dist[c];
    cout << min({da, db, dc}) << " " << max({da, db, dc}) << "\n";

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            if (u != v) { // 跳过自环
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }

        // 从宝藏节点 t 出发做 BFS
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        dist[t] = 0;
        q.add(t);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }

        int da = dist[a], db = dist[b], dc = dist[c];
        int mn = Math.min(da, Math.min(db, dc));
        int mx = Math.max(da, Math.max(db, dc));
        System.out.println(mn + " " + mx);
    }
}