首页 > 试题广场 >

星际跃迁网络

[编程题]星际跃迁网络
  • 热度指数：289 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个广袤的宇宙中，存在一个由 N 个星系组成的星际网络，星系编号从 0 开始。
探险家们依赖 M 条不同的“跃迁航线”在星系间穿梭。每条跃迁航线都连接着多个星系。

如果两条不同的跃迁航线都经过同一个星系，那么探险家就可以在该星系从一条航线切换到另一条，我们称之为一次“航线换乘”。
现在，给定一系列的星际旅行任务，每个任务包含一个起始星系和一个目标星系，请计算出完成每个任务所需的最少航线换乘次数。

输入描述:
第一行包含三个整数 N、M 和 K，分别代表星系的总数量、跃迁航线的总数量以及需要查询的旅行任务数量。

接下来 M 行，每行描述一条跃迁航线。
行首是一个整数 C，表示该航线连接的星系数量，随后是 C 个整数，代表这些星系的编号。

再接下来 K 行，每行包含两个整数 S 和 T，分别代表一个旅行任务的起始星系和目标星系。

所有变量的取值范围均为 [0, 1000]。


输出描述:
对于每个查询任务，输出一个整数，即从起始星系 S 到目标星系 T 所需的最少换乘次数。
如果无法从 S 到达 T，则输出 -1。
示例1

输入

19 9 6
5 5 8 10 13 18
4 1 5 7 9
2 9 10
7 1 5 6 7 12 15 16
7 0 4 6 8 13 14 17
6 3 4 10 15 16 18
9 2 3 6 7 8 9 12 14 17
5 1 3 7 9 11
9 3 5 6 8 9 10 14 15 18
2 5
1 8
10 6
5 12
5 7
17 8

输出

1
1
0
0
0
0

备注:
本题由牛友@Charles 整理上传
算法知识视频讲解
添加回答
牛客797878号头像 牛客797878号
#include <iostream>
#include <set>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    int c;
    vector<set<int>> num(n);
    //vector<vector<int>> pos(k);
    for (int i = 0; i < m; i++) {
        int c;
        cin >> c;
        set<int> tmp;
        for (int j = 0; j < c; j++) {
            int b;
            cin >> b;
            tmp.insert(b);
        }
        for (auto it : tmp) {
            num[it].insert(tmp.begin(), tmp.end());
            //num[it].erase(it);前面过了90%，去掉这句就全过了
        }
    }
    for (int i = 0; i < k; i++) {
        int start, last;
        cin >> start >> last;
        int count = 0;
        bool flag = false;
        if (num[start].find(last) != num[start].end()) {
            cout << 0 << endl;
            continue;
        } else {
            set<int> quchong;
            quchong.insert(num[start].begin(), num[start].end());
            auto quc = quchong.begin();
            set<int> quchong1;
            vector<bool> used(n, false);
            while (quc != quchong.end()) {
                int st1num = *quc;
                used[st1num] = true;
                if (num[st1num].find(last) != num[st1num].end()) {
                    flag = true;
                } else {
                    for (auto it : num[st1num]) {
                        if (!used[it]) quchong1.insert(it);
                    }
                }
                if (flag) {
                    count++;
                    cout << count << endl;
                    break;
                } else {
                    quc++;
                    if (quc == quchong.end()) {
                        quchong.clear();
                        quchong.insert(quchong1.begin(), quchong1.end());
                        quc = quchong.begin();
                        quchong1.clear();
                        count++;
                    }
                }
            }
        }
        if(!flag) cout << -1 << endl;
    }
    /*for (int i = 0; i < n; i++) {
        cout << i << " :";
        for (set<int>::iterator it = num[i].begin(); it != num[i].end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }*/
}
// 64 位输出请用 printf("%lld")
发表于 2025-10-25 17:21:45 回复(0)
提交观点

问题信息

难度：
1条回答 48浏览

热门推荐

相关试题

星际跃迁网络

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号