「NOIP模拟赛」虫洞

2014年5月10日5,0710

「题目描述」

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的路线。

题解

首先每个点拆成黑白点

本来一个黑到一个白连边v+delta

但是因为每秒会变色,所以是一个黑到一个黑连边v+delta

条件是俩点的初始颜色不同

其余的同理

然后最短路。。。

一开始spfa写错只有80分好伤心。。

 

avatar
  Subscribe  
提醒