Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


codevs伊吹萃香

题目链接

题目描述

在幻想乡,伊吹萃香是能够控制物体密度的鬼王。因为能够控制密度,所以萃香能够制造白洞和黑洞,并可以随时改变它们。某一天萃香闲着无聊,在妖怪之山上设置了一些白洞或黑洞,由于引力的影响,给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路,来方便进出。已知妖怪之山上有N个路口(编号1..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的体力。

输出描述

第1行:1个整数,表示消耗的最小体力

解题思路

其余的不怎么难,难点就在于如何使黑洞变成白洞或者黑洞走到白洞一类复杂的东西。
对于每一个”洞”,我们不知道它是那种洞,所以我们干脆将这个洞分成一白一黑两个洞。
设i为白洞,i+N为黑洞,那么我们需要这样建图:
①将第i个点的黑洞白洞连起来(在这个洞等一时刻)
②将这些点按照给定的输入连起来,注意它的另外一种洞也要与对面的另外一种洞连起来。
然后对于这样的一个图来说,我们只需要跑最短路就可以了,注意最后只要在编号为N的洞就好,不关心它是哪一个洞。
所以要取min(dis[end],dis[end+N])//编号为end的洞是黑洞或者白洞。
还有一个要注意的就是col[1]是黑洞我们要从1+N做,否则从1做

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
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
void read(int &x){
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
struct H {
int to;
int dis;
}o;
vector <H> z[100005];
deque <int> q;
int n,m,w[10005],s[10005],dis[10005];
bool inq[10005],col[10005];
void spfa(int rt){
if(col[rt] == 1) rt += n;
memset(dis,127,sizeof(dis));
dis[rt] = 0;
q.push_back(rt);
inq[rt] = true;
while(!q.empty()){
int x = q.front();
for(int i = 0;i < z[x].size();i++){
if(dis[z[x][i].to] > dis[x] + z[x][i].dis){
dis[z[x][i].to] = dis[x] + z[x][i].dis;
if(!inq[z[x][i].to]){
q.push_back(z[x][i].to);
inq[z[x][i].to] = true;
}
}
}
q.pop_front();
inq[x] = false;
}
}
int main(){
int u,v,k;
read(n),read(m);
for(int i = 1;i <= n;i++) scanf("%d",&col[i]);
for(int i = 1;i <= n;i++) read(w[i]);
for(int i = 1;i <= n;i++) read(s[i]);
for(int i = 1;i <= m;i++){
read(u),read(v),read(k);
if(col[u] == col[v]){
o.to = v+n;o.dis = k;
z[u].push_back(o);
o.to = v;o.dis = k;
z[u+n].push_back(o);
}
else {
int tmp = abs(w[u]-w[v]);
o.to = v+n;o.dis = k+tmp;
z[u+n].push_back(o);
o.to = v;o.dis = max(0,k-tmp);
z[u].push_back(o);
}
}
for(int i = 1;i <= n;i++){
o.to = i+n;o.dis = 0;
z[i].push_back(o);
o.to = i;o.dis = s[i];
z[i].push_back(o);
}
spfa(1);
printf("%d",dis[n]);
return 0;
}

Markdown

最近的文章

[codevs]1082线段树3

线段树区间修改求和模板题目链接题目描述 给你N个数,有两种操作:1:给区间[a,b]的所有数增加X2:询问区间[a,b]的数的和。 输入描述 第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,每行表示操作的个数,如果第一个数是1,后接3个正整数,表示在区间[a,b]内每个数增加X,如果 …

于  线段树 继续阅读
更早的文章

book解题报告

问题描述 暑假到了,Rick制定了一个长达M天的阅读计划。他一共有N本书,从1至N进行标号;Rick将它们从上至下摞成一堆。他每天都会读一本书,假设他要读编号为X的书,他会按照以下步骤:1,将这本书上方的所有书搬起来。2,将这本书拿出来3,将搬起来的书挪回去。4,看完后把这本书放到顶端。 每本书都会 …

于  贪心 继续阅读