虫洞 (holes. cpp/c/pas)
题目描述
N 个虫洞, M 条单向跃迁路径. 从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和 1 单位时间. 虫洞有白洞和黑洞之分. 设一条跃迁路径两端的虫洞质量差为 delta.
- 从白洞跃迁到黑洞, 消耗的燃料值减少 delta, 若该条路径消耗的燃料值变为负数的话, 取为 0.
- 从黑洞跃迁到白洞, 消耗的燃料值增加 delta.
- 路径两端均为黑洞或白洞, 消耗的燃料值不变化.
作为压轴题, 自然不会是如此简单的最短路问题, 所以每过 1 单位时间黑洞变为白洞, 白洞 变为黑洞. 在飞行过程中, 可以选择在一个虫洞停留 1 个单位时间, 如果当前为白洞, 则不 消耗燃料, 否则消耗 s [i] 的燃料. 现在请你求出从虫洞 1 到 N 最少的燃料消耗, 保证一定存在 1 到 N 的路线.
输入格式
第 1 行: 2 个正整数 N, M
第 2 行: N 个整数, 第 i 个为 0 表示虫洞 i 开始时为白洞, 1 表示黑洞.
第 3 行: N 个整数, 第 i 个数表示虫洞 i 的质量 w [i].
第 4 行: N 个整数, 第 i 个数表示在虫洞 i 停留消耗的燃料 s [i].
第 5...... M+4 行: 每行 3 个整数, u, v, k, 表示在没有影响的情况下, 从虫洞 u 到虫洞 v 需要消耗燃料 k.
输出格式
一个整数, 表示最少的燃料消耗.
样例输入
4 5
1 0 1 0
10 10 100 10
5 20 15 10
1 2 30
2 3 40
1 3 20
1 4 200
3 4 200样例输出
130数据范围
对于 30% 的数据:\(1 \leq N \leq 100, 1 \leq M \leq 500\)
对于 60% 的数据:\(1 \leq N \leq 1000,1 \leq M \leq 5000\)
对于 100% 的数据:\(1 \leq N \leq 5000，1 \leq M \leq 30000\)
\(1 \leq u, v \leq N, 1 \leq k, w[i], s[i] \leq 200\)
其中 20% 的数据为 \(1 \leq N \leq 3000\) 的链
样例说明
按照 1->3->4 的路线.
Explanation
将每一个节点拆成两个点, 即其在白洞的状态和在黑洞的状态, 各一个.
然后考虑时间的变化后分类讨论, 在原来的两个点拆出来的四个点之间建边 (具体参见源码 的 addedge 函数等等).
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 150100;
const lli infinit = 0x007f7f7f7f7f7f7fll;
class SPFA
{
public:
struct edge {
int u, v;
lli len;
edge *next;
} *edges[maxn], epool[maxm];
int n, s, cnt;
lli dist[maxn];
bool inque[maxn];
void addedge(int u, int v, lli len)
{
// printf("addedge %d -> %d : %lld\n", u, v, len);
edge *p = &epool[++cnt];
p->u = u; p->v = v; p->len = len;
p->next = edges[u]; edges[u] = p;
return ;
}
void eval(void)
{
for (int i = 1; i <= n; i++)
dist[i] = infinit,
inque[i] = false;
queue<int> que;
que.push(s);
dist[s] = 0, inque[s] = true;
while (!que.empty()) {
int p = que.front();
que.pop();
for (edge *ep = edges[p]; ep; ep = ep->next)
if (dist[p] + ep->len < dist[ep->v]) {
dist[ep->v] = dist[p] + ep->len;
if (!inque[ep->v]) {
que.push(ep->v);
inque[ep->v] = true;
}
}
inque[p] = false;
continue;
}
// Results must be retrieved manually by user from dist[...].
return ;
}
} graph;
int n, m;
bool I[maxn]; // Initial state (white: false, black: true)
lli W[maxn]; // Mass of the wormhole
lli S[maxn]; // The cost of staying at this wormhole
int main(int argc, char** argv)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &I[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &W[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &S[i]);
// Here comes the addedge... which is a difficult thing to do
// Graph is oriented in such a way:
// 2 * i - 1 -> wormhole #i @ state white hole
// 2 * i -> wormhole #i @ state black hole
graph.n = n * 2;
graph.s = I[1] ? 2 : 1;
// The following procedures determine how much cost would be dealt when
// warping between wormholes.
for (int i = 1, u, v; i <= m; i++) {
lli k;
scanf("%d%d%lld", &u, &v, &k);
// If both are of the same type... otherwise...
if (I[u] == I[v]) {
// Warping from white to what would be a white hole
graph.addedge(2 * u - 1, 2 * v, k);
// Warping from black to what would be a black hole
graph.addedge(2 * u, 2 * v - 1, k);
} else {
// Warping from white hole to what would be a black hole
graph.addedge(2 * u - 1, 2 * v - 1, max(0ll, k - abs(W[u] - W[v])));
// Warping from black hole to what would be a white hole
graph.addedge(2 * u, 2 * v, k + abs(W[u] - W[v]));
}
}
// The following procedures determine how much cost would be dealt when
// staying at the same wormhole.
for (int i = 1; i <= n; i++) {
// At time this is a white hole
graph.addedge(2 * i - 1, 2 * i, 0);
// At time this is a black hole
graph.addedge(2 * i, 2 * i - 1, S[i]);
}
// Execute shortest path with SPFA.
graph.eval();
// for (int i = 1; i <= graph.n; i++)
// printf("#%d -> %lld;\n", i, graph.dist[i]);
lli res = min(
graph.dist[2 * n - 1],
graph.dist[2 * n]);
printf("%lld\n", res);
return 0;
}