题目链接

虫洞网络

题目描述

在宇宙中，有 个独立的虫洞网络。要进入任何一个网络，都需要消耗特定的能量。一旦进入，飞船就可以在该网络内的所有星系间无消耗地穿梭。

给定一个起点星系 和一个目标星系 ，以及飞船的总备用能量 。任务是计算从 到 所需的最小总能量消耗。

  • 一次旅行可能需要穿越多个虫洞网络。
  • 如果无法抵达，或最低能量消耗超过 ，则视为任务失败。

解题思路

这是一个最短路径问题。如果直接将星系作为图的节点，同一个虫洞网络内的所有星系都会形成一个完全连通的子图，边数会非常多，导致效率低下。

更高效的方法是构建一个包含两种不同类型节点的图：星系节点和虫洞网络节点。

1. 构建混合图模型

  • 节点 (Nodes)：

    1. 为每一个在题目中出现的星系创建一个“星系节点”。
    2. 为每一个虫洞网络创建一个“虫洞网络节点”。为了在同一个数组中区分它们，我们可以约定星系 g 的节点编号就是 g，而第 i 个虫洞网络（）的节点编号是 MAX_GALAXY_ID + i。

  • 边 (Edges)： 根据旅行规则建立有向边和权重：

    1. 从星系到网络：对于每一个在网络 i（成本为 ）中的星系 g，我们建立一条从“星系节点 g” 到 “网络节点 i” 的有向边。这条边的权重是 ，代表支付能量以激活并进入该虫洞网络。
    2. 从网络到星系：对于同一个星系 g 和网络 i，我们再建立一条从“网络节点 i” 到 “星系节点 g” 的反向边。这条边的权重是 ，代表在已激活的网络内移动是无消耗的。

2. 应用 Dijkstra 算法

构建好这个混合图后，问题就转化为了一个标准的单源最短路径问题。

  • 起点：起始星系 对应的“星系节点”。
  • 算法：我们从起点 开始，运行 Dijkstra 算法，计算到图中所有其他节点的最短路径（最小能量消耗）。
  • 状态：算法中的 dist[v] 数组记录了从起点 到达节点 v（无论是星系节点还是网络节点）所需的最小总能量。

3. 确定最终结果

  • Dijkstra 算法结束后，dist[t] 的值就是从星系 到达星系 的最小能量消耗。
  • 最后，将这个结果与飞船的总备用能量 进行比较：
    • 如果 dist[t] 是一个有效值（不是无穷大）且 dist[t] <= e，则输出 dist[t]。
    • 否则，说明无法抵达或能量不足，输出 -1。

这个模型巧妙地将网络内的“任意穿梭”特性转化为了“网络节点 -> 星系节点”的 0 权重边，从而可以用标准的最短路算法高效求解。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

using ll = long long;
using P = pair<ll, int>;

const int MAX_GALAXY_ID = 50000;
const ll INF = 1e18;

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

    int n, s, t;
    ll e;
    cin >> n >> s >> t >> e;

    int max_node_id = MAX_GALAXY_ID + n;
    vector<vector<P>> adj(max_node_id + 1);
    
    for (int i = 0; i < n; ++i) {
        ll cost;
        int k;
        cin >> cost >> k;
        int network_node_id = MAX_GALAXY_ID + i + 1;
        for (int j = 0; j < k; ++j) {
            int galaxy_id;
            cin >> galaxy_id;
            // 从星系 -> 网络，成本为 cost
            adj[galaxy_id].push_back({cost, network_node_id});
            // 从网络 -> 星系，成本为 0
            adj[network_node_id].push_back({0, galaxy_id});
        }
    }

    vector<ll> dist(max_node_id + 1, INF);
    priority_queue<P, vector<P>, greater<P>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) {
            continue;
        }

        for (auto& edge : adj[u]) {
            int v = edge.second;
            ll weight = edge.first;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[t] == INF || dist[t] > e) {
        cout << -1 << endl;
    } else {
        cout << dist[t] << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    static final int MAX_GALAXY_ID = 50000;
    static final long INF = (long) 1e18;

    static class Edge {
        int to;
        long cost;

        Edge(int to, long cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int t = sc.nextInt();
        long e = sc.nextLong();

        int maxNodeId = MAX_GALAXY_ID + n;
        List<List<Edge>> adj = new ArrayList<>(maxNodeId + 1);
        for (int i = 0; i <= maxNodeId; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            long cost = sc.nextLong();
            int k = sc.nextInt();
            int networkNodeId = MAX_GALAXY_ID + i + 1;
            for (int j = 0; j < k; j++) {
                int galaxyId = sc.nextInt();
                adj.get(galaxyId).add(new Edge(networkNodeId, cost));
                adj.get(networkNodeId).add(new Edge(galaxyId, 0));
            }
        }

        long[] dist = new long[maxNodeId + 1];
        Arrays.fill(dist, INF);
        
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));

        dist[s] = 0;
        pq.add(new long[]{0, s});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int u = (int) current[1];

            if (d > dist[u]) {
                continue;
            }

            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                long weight = edge.cost;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new long[]{dist[v], v});
                }
            }
        }

        if (dist[t] == INF || dist[t] > e) {
            System.out.println(-1);
        } else {
            System.out.println(dist[t]);
        }
    }
}

import heapq

def solve():
    MAX_GALAXY_ID = 50000
    INF = float('inf')

    n, s, t, e = map(int, input().split())

    max_node_id = MAX_GALAXY_ID + n
    adj = [[] for _ in range(max_node_id + 1)]

    for i in range(n):
        line = list(map(int, input().split()))
        cost, k = line[0], line[1]
        galaxies = line[2:]
        network_node_id = MAX_GALAXY_ID + i + 1
        for galaxy_id in galaxies:
            adj[galaxy_id].append((cost, network_node_id))
            adj[network_node_id].append((0, galaxy_id))

    dist = [INF] * (max_node_id + 1)
    pq = [(0, s)]
    dist[s] = 0

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for weight, v in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

    result = dist[t]
    if result == INF or result > e:
        print(-1)
    else:
        print(result)

solve()

算法及复杂度

  • 算法：图建模 + Dijkstra 算法
  • 时间复杂度：，其中 是虫洞网络的数量， 是所有涉及到的星系的最大编号（本题中为 50000）， 是所有网络中星系列表的长度总和。建图的时间复杂度为 。Dijkstra 算法的复杂度取决于节点和边的数量。节点总数为 ，边的总数为 ，因此 Dijkstra 的复杂度为 。
  • 空间复杂度：，主要用于存储图的邻接表和 Dijkstra 算法所需的距离数组。