虫洞网络
题意
有 个虫洞网络,每个网络连接若干星系,激活需要一定能量。一旦激活某个网络,就能在该网络内的所有星系之间免费瞬移。
给定起点星系 、终点星系
、总能量
,求从
到
的最小能量消耗。如果无法到达或能量不够,输出
。
思路
每个虫洞网络把一组星系"打包"在一起,付一次费就能在组内任意跳。怎么建模?
最直接的想法:同一网络内任意两个星系之间连一条边,权值为激活成本。但如果一个网络有 个星系,就要连
条边,太多了。
更聪明的做法是引入虚拟节点。为每个网络创建一个虚拟节点,然后:
- 每个星系
虚拟节点:边权 = 该网络的激活成本(表示"花钱进入这个网络")
- 虚拟节点
每个星系:边权 = 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]);
});

京公网安备 11010502036488号