AHSOFNU NOIP模拟题-2 T3(拆点最短路)

SPFA最好不要动松弛,使用加边拆点等来完成题目,更不要修改边权
把一个虫洞拆成两个点,$i$为白洞,$i+n$为黑洞
对于停留,连边$i -> i+n$,权值为$0$,连边$i+n -> i$,权值为$s$,其实停留就是从这个点的白洞走向黑洞或者黑洞走向白洞
对于两个路径上的洞,由于洞的属性会变,所以从白洞到黑洞其实是白洞到白洞,这里不作具体解释了,请看代码中相关部分。
接下来求个最短路就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "holes"
using namespace std;
const int MAXN = 5000 + 5, MAXM = 30000 + 5;
struct data{int v, wi;}e[MAXM*10];
vector<int> G[MAXN*3];
int n, m, en, p[MAXN*3], zl[MAXN*3], vi[MAXN*3], dis[MAXN*3];
void ins(int u, int v, int wi) {//i is while hole, i+n is black hole.
en++, e[en].v = v, e[en].wi = wi, G[u].push_back(en);
}
void spfa() {
queue<int> q;
ms(dis, 127), ms(vi, 0), dis[p[1]*n+1] = 0, vi[p[1]*n+1] = true, q.push(p[1]*n+1);
while (!q.empty()) {
int u = q.front(); q.pop(); vi[u] = false;
for (int i=0;i<G[u].size();i++) {
data r = e[G[u][i]];
int v = r.v, wi = r.wi;
if (dis[v] > dis[u]+wi) {
dis[v] = dis[u]+wi;
if (!vi[v]) vi[v] = true, q.push(v);
}
}
}
printf("%d\n", min(dis[n], dis[n+n]));
}
void clean() {
en = 0;
for (int i=0;i<=n;i++) G[i].clear();
}
void solve() {
clean();
scanf("%d%d", &n, &m);
for (int i=1;i<=n;i++) scanf("%d", &p[i]);
for (int i=1;i<=n;i++) scanf("%d", &zl[i]);
for (int i=1;i<=n;i++) {
int t; scanf("%d", &t);
ins(i, i+n, 0), ins(i+n, i, t);//对应停留
}
for (int i=1;i<=m;i++) {
int u, v, k, t;
scanf("%d%d%d", &u, &v, &k); t = abs(zl[u] - zl[v]);
if (p[u]==p[v]) ins(u, v+n, k), ins(u+n, v, k);
else ins(u, v, (k-t>=0) ? (k-t) : 0), ins(u+n, v+n, k+t);
}
spfa();
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
solve();
fclose(stdin); fclose(stdout);
return 0;
}

Problem 3 虫洞(holes.cpp/c/pas)
【题目描述】
N个虫洞,M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。
1.从白洞跃迁到黑洞,消耗的燃料值减少delta,若该条路径消耗的燃料值变为负数的话,取为0。
2.从黑洞跃迁到白洞,消耗的燃料值增加delta。
3.路径两端均为黑洞或白洞,消耗的燃料值不变化。
作为压轴题,自然不会是如此简单的最短路问题,所以每过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<=N<=100,1<=M<=500
对于60%的数据: 1<=N<=1000,1<=M<=5000
对于100%的数据: 1<=N<=5000,1<=M<=30000
其中20%的数据为1<=N<=3000的链
1<=u,v<=N, 1<=k,w[i],s[i]<=200
【样例说明】
按照1->3->4的路线。

------ 本文结束 ------