类似的需要建立虚拟节点的题目可以参考:
https://www.acwing.com/problem/content/description/458/
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 300010, M = 600100;
int head[N], ver[M], edge[M], Next[M], d[N];//模板
bool v[N];//模板
int n, m, c, tot;//模板
void add(int x, int y, int z) {//模板
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
void dijkstra() {//模板
priority_queue<pii, vector<pii>, greater<pii>> q;
d[1] = 0, q.push(make_pair(0, 1));
while (q.size()) {
// 取出堆顶
int x = q.top().second; q.pop();
if (v[x]) continue; v[x] = 1;
// 扫描所有出边
if(x == n) return ;
for (int i = head[x]; i; i = Next[i]) {
int y = ver[i], z = edge[i];
if (d[y] > d[x] + z) {
// 更新,把新的二元组插入堆
d[y] = d[x] + z;
q.push(make_pair(d[y], y));
}
}
}
}
int main(){
int tt; scanf("%d", &tt);
for(int ttt = 1; ttt <= tt; ttt++) {
scanf("%d%d%d", &n, &m, &c);
int sk = n + 3;
tot = 1;//没加tot = 1 tmd一直TLE
for(int i = 1; i <= sk * 3; i++) head[i] = 0, d[i] = 0x3f3f3f3f, v[i] = 0; //初始化
// 初始化方法二:
// memset(head, 0, sizeof head);
// memset(v, 0, sizeof v);
// memset(d, 0x3f, sizeof d);
// 普通点: 1 - n,向下走的虚拟点: [sk, sk + n + 1], 向上走的虚拟点:[sk * 2, sk * 2 + n + 1]
for(int i = 1; i <= n; i++){
int lev; scanf("%d", &lev);
add(i, sk + lev, 0), add(i, sk * 2 + lev + 1, 0);
add(sk * 2 + lev, i, c), add(sk + lev + 1, i, c);
}
// 建立虚拟节点方法二:将每一层多一个虚拟节点作为其“层入点”
// for(int i = 1; i <= n; i++){
// int lev; scanf("%d", &lev);
// add(i, sk + lev - 1, 0), add(i, sk + lev + 1, 0);
// add(sk + lev, i, c);
// }
for (int i = 1; i <= m; i++) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
add(x, y, z), add(y, x, z);
}
dijkstra();
printf("Case #%d: %d", ttt, (d[n] == 0x3f3f3f3f ? -1: d[n])); cout << endl;
}
return 0;
}