算法
(虚拟节点 + dijkstra) $O(mlogn)$
原始思路:如果两个点在相邻两层,则加边,但是假如说上层有1e5
个点,下层有1e5
个点,那肯定会超出内存限制
在此基础上,新的思路:建立虚拟节点连接两层,下层->dummy->上层
,原来$O(n^2)$级别的点就变成$O(n)$级别的边
关于建立虚拟节点的方式:
将N
翻倍,节点范围变成1~2n
,i
对应虚拟节点i + n + 1
add(i, level[i] + n + 1, 0); // 单向边,保证同层的节点距离不是0
add(level[i] + n + 1 + 1, i, C); // 正常的加边操作1, dummy->下层
add(level[i] + n + 1 - 1, i, C); // 正常的加边操作2, dummy->上层
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, M = N * 3, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int n, m, C;
int level[N];
bool st[N];
int dist[N];
void init()
{
memset(h, -1, sizeof h);
idx = 0;
}
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, 1});
dist[1] = 0;
while(q.size())
{
auto [d, ver] = q.top();
q.pop();
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > d + w[i])
{
dist[j] = d + w[i];
q.push({dist[j], j});
}
}
}
if(dist[n] == INF) return -1;
return dist[n];
}
int main()
{
int T;
cin >> T;
for(int cases = 1; cases <= T; cases++)
{
init();
cin >> n >> m >> C;
for(int i = 1; i <= n; i++) cin >> level[i];
for(int i = 1; i <= n; i++)
{
add(i, level[i] + n + 1, 0);
add(level[i] + n + 1 + 1, i, C);
add(level[i] + n + 1 - 1, i, C);
}
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
int res = dijkstra();
printf("Case #%d: %d\n", cases, res);
}
return 0;
}