虫洞网络

题意

个虫洞网络,每个网络连接若干星系,激活需要一定能量。一旦激活某个网络,就能在该网络内的所有星系之间免费瞬移。

给定起点星系 、终点星系 、总能量 ,求从 的最小能量消耗。如果无法到达或能量不够,输出

思路

每个虫洞网络把一组星系"打包"在一起,付一次费就能在组内任意跳。怎么建模?

最直接的想法:同一网络内任意两个星系之间连一条边,权值为激活成本。但如果一个网络有 个星系,就要连 条边,太多了。

更聪明的做法是引入虚拟节点。为每个网络创建一个虚拟节点,然后:

  • 每个星系 虚拟节点:边权 = 该网络的激活成本(表示"花钱进入这个网络")
  • 虚拟节点 每个星系:边权 = 0(表示"进了网络后可以免费到达任意星系")

这样每个网络只需要 条边,总边数是线性的。

建好图之后,跑一遍 Dijkstra 最短路 就行了。注意星系编号可能很大(到 ),用哈希表做坐标压缩,把所有出现过的星系映射到连续编号。

最后比较最短距离和能量上限 ,如果最短路不存在或者超过 就输出

时间复杂度 ,其中 是所有网络包含的星系总数。

代码

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

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

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

    unordered_map<int, int> idMap;
    int idx = 0;
    auto getId = [&](int x) -> int {
        auto it = idMap.find(x);
        if(it != idMap.end()) return it->second;
        return idMap[x] = idx++;
    };

    getId(s);
    getId(t);

    struct Network { int cost, cnt; vector<int> systems; };
    vector<Network> nets(n);
    for(int i = 0; i < n; i++){
        cin >> nets[i].cost >> nets[i].cnt;
        nets[i].systems.resize(nets[i].cnt);
        for(int j = 0; j < nets[i].cnt; j++){
            cin >> nets[i].systems[j];
            getId(nets[i].systems[j]);
        }
    }

    int systemCount = idx;
    int totalNodes = systemCount + n;
    vector<vector<pair<int,int>>> adj(totalNodes);

    for(int i = 0; i < n; i++){
        int vnode = systemCount + i;
        for(int j = 0; j < nets[i].cnt; j++){
            int sid = idMap[nets[i].systems[j]];
            adj[sid].push_back({vnode, nets[i].cost});
            adj[vnode].push_back({sid, 0});
        }
    }

    int sId = idMap[s], tId = idMap[t];
    vector<long long> dist(totalNodes, LLONG_MAX);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dist[sId] = 0;
    pq.push({0, sId});

    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        if(u == tId) break;
        for(auto [v, w] : adj[u]){
            long long nd = d + w;
            if(nd < dist[v]){
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }

    if(dist[tId] == LLONG_MAX || dist[tId] > e)
        cout << -1 << endl;
    else
        cout << dist[tId] << endl;
    return 0;
}
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);

        in.nextToken(); int n = (int)in.nval;
        in.nextToken(); int s = (int)in.nval;
        in.nextToken(); int t = (int)in.nval;
        in.nextToken(); long e = (long)in.nval;

        HashMap<Integer, Integer> idMap = new HashMap<>();
        int[] idx = {0};
        idMap.put(s, idx[0]++);
        if (!idMap.containsKey(t)) idMap.put(t, idx[0]++);

        int[][] netSystems = new int[n][];
        int[] netCost = new int[n];

        for (int i = 0; i < n; i++) {
            in.nextToken(); netCost[i] = (int)in.nval;
            in.nextToken(); int cnt = (int)in.nval;
            netSystems[i] = new int[cnt];
            for (int j = 0; j < cnt; j++) {
                in.nextToken(); int sys = (int)in.nval;
                if (!idMap.containsKey(sys)) idMap.put(sys, idx[0]++);
                netSystems[i][j] = sys;
            }
        }

        int systemCount = idx[0];
        int totalNodes = systemCount + n;
        List<int[]>[] adj = new ArrayList[totalNodes];
        for (int i = 0; i < totalNodes; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int vnode = systemCount + i;
            for (int j = 0; j < netSystems[i].length; j++) {
                int sid = idMap.get(netSystems[i][j]);
                adj[sid].add(new int[]{vnode, netCost[i]});
                adj[vnode].add(new int[]{sid, 0});
            }
        }

        int sId = idMap.get(s), tId = idMap.get(t);
        long[] dist = new long[totalNodes];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[sId] = 0;

        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, sId});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0]; int u = (int)cur[1];
            if (d > dist[u]) continue;
            if (u == tId) break;
            for (int[] edge : adj[u]) {
                long nd = d + edge[1];
                if (nd < dist[edge[0]]) {
                    dist[edge[0]] = nd;
                    pq.offer(new long[]{nd, edge[0]});
                }
            }
        }

        System.out.println(dist[tId] == Long.MAX_VALUE || dist[tId] > e ? -1 : dist[tId]);
    }
}
import sys
import heapq

def main():
    first = sys.stdin.readline().split()
    n, s, t, e = int(first[0]), int(first[1]), int(first[2]), int(first[3])

    idMap = {}
    idx = 0

    def getId(x):
        nonlocal idx
        if x not in idMap:
            idMap[x] = idx
            idx += 1
        return idMap[x]

    getId(s)
    getId(t)

    networks = []
    for _ in range(n):
        parts = list(map(int, sys.stdin.readline().split()))
        cost, cnt = parts[0], parts[1]
        systems = parts[2:2+cnt]
        for sys_id in systems:
            getId(sys_id)
        networks.append((cost, systems))

    systemCount = idx
    totalNodes = systemCount + n
    adj = [[] for _ in range(totalNodes)]

    for i, (cost, systems) in enumerate(networks):
        vnode = systemCount + i
        for sys_id in systems:
            sid = idMap[sys_id]
            adj[sid].append((vnode, cost))
            adj[vnode].append((sid, 0))

    sId, tId = idMap[s], idMap[t]
    dist = [float('inf')] * totalNodes
    dist[sId] = 0
    pq = [(0, sId)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == tId:
            break
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    print(-1 if dist[tId] == float('inf') or dist[tId] > e else dist[tId])

main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];

rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, s, t, e] = lines[0].split(/\s+/).map(Number);

    const idMap = new Map();
    let idx = 0;
    const getId = (x) => {
        if (!idMap.has(x)) idMap.set(x, idx++);
        return idMap.get(x);
    };
    getId(s); getId(t);

    const networks = [];
    for (let i = 0; i < n; i++) {
        const parts = lines[i + 1].split(/\s+/).map(Number);
        const cost = parts[0], cnt = parts[1];
        const systems = parts.slice(2, 2 + cnt);
        for (const sys of systems) getId(sys);
        networks.push({ cost, systems });
    }

    const systemCount = idx, totalNodes = systemCount + n;
    const adj = Array.from({ length: totalNodes }, () => []);

    for (let i = 0; i < n; i++) {
        const vnode = systemCount + i;
        for (const sys of networks[i].systems) {
            const sid = idMap.get(sys);
            adj[sid].push([vnode, networks[i].cost]);
            adj[vnode].push([sid, 0]);
        }
    }

    const sId = idMap.get(s), tId = idMap.get(t);
    const dist = new Array(totalNodes).fill(Infinity);
    dist[sId] = 0;

    // Binary min-heap
    class MinHeap {
        constructor() { this.d = []; }
        push(v) {
            this.d.push(v);
            let i = this.d.length - 1;
            while (i > 0) {
                const p = (i - 1) >> 1;
                if (this.d[p][0] <= this.d[i][0]) break;
                [this.d[p], this.d[i]] = [this.d[i], this.d[p]];
                i = p;
            }
        }
        pop() {
            const top = this.d[0], last = this.d.pop();
            if (this.d.length > 0) {
                this.d[0] = last;
                let i = 0;
                while (true) {
                    let s = i, l = 2*i+1, r = 2*i+2;
                    if (l < this.d.length && this.d[l][0] < this.d[s][0]) s = l;
                    if (r < this.d.length && this.d[r][0] < this.d[s][0]) s = r;
                    if (s === i) break;
                    [this.d[s], this.d[i]] = [this.d[i], this.d[s]];
                    i = s;
                }
            }
            return top;
        }
        get size() { return this.d.length; }
    }

    const pq = new MinHeap();
    pq.push([0, sId]);

    while (pq.size > 0) {
        const [d, u] = pq.pop();
        if (d > dist[u]) continue;
        if (u === tId) break;
        for (const [v, w] of adj[u]) {
            const nd = d + w;
            if (nd < dist[v]) { dist[v] = nd; pq.push([nd, v]); }
        }
    }

    console.log(dist[tId] === Infinity || dist[tId] > e ? -1 : dist[tId]);
});