|
题目描述 |
在幻想乡，伊吹萃香（いぶき すいか）是能够控制物体密度的鬼王。因为能够控制密度，所以萃香能够制造白洞和黑洞，并可以随时改变它们。某一天萃香闲着无聊，在妖怪之山上设置了一些白洞或黑洞，由于引力的影响，给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路，来方便进出。已知妖怪之山上有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个整数，表示消耗的最小体力 |
|
|
输入样例 |
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 <= 1,000, 1 <= M <= 5,000 对于100%的数据：1 <= N <= 5,000, 1 <= M <= 30,000 其中20%的数据为1 <= N <= 3000的链 1 <= u,v <= N, 1 <= k,w[i],s[i] <= 200 |
|
|
样例说明 |
按照1 -> 3 -> 4的路线。 |
|
【题解】
二维spfa，spfa最近出镜率有点高，聪聪和可可刚用spfa做了预处理，又出现了一道二维spfa。题目看似很复杂，变来变去，其实时间只有奇数和偶数两种状态，比起原来传送门还有25种状态还是好些。spfa松弛时颜色相同的直接按原边权，颜色不同的对两种状态分别处理，最后还有一种留在原地的情况。二维spfa除了队列中要存结构体、dis和r数组都开成二维之外并没有什么特别之处，但这道题的分类讨论还是被我写得十分之麻烦。zzh的代码直接把都只有01的时间与点对应起来，用亦或实现0与1的转换，简洁了不少(虽说他最后并没有用这种常规图论做法过)。从移动玩具和这道题就能看出来我仿佛总是把情况分得过于细，注意不到一些可以合并的情况和可以利用的性质，所以做题的效率可能很低，这次要不是把入队打了个函数恐怕也要打上150行。谋定而后动，在做题的时候尚可以追求，考试就比较难了吧。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<cmath> using namespace std; const int sj=5010; int n,m,a1,a2,a3,w[sj],sa[sj],h[sj],e,dis[sj][2]; bool hd[sj],r[sj][2]; struct QK { int xi,ci; bool operator < (const QK &b) const { return dis[xi][ci]>dis[b.xi][b.ci]; } }; priority_queue<QK> s; struct B { int ne,v,w; }b[sj*6]; void add(int x,int y,int z) { b[e].v=y; b[e].w=z; b[e].ne=h[x]; h[x]=e++; } void init() { scanf("%d%d",&n,&m); memset(dis,0x3f,sizeof(dis)); memset(h,-1,sizeof(h)); for(int i=1;i<=n;i++) scanf("%d",&hd[i]); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) scanf("%d",&sa[i]); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a1,&a2,&a3); add(a1,a2,a3); } } void rd(int x,int y) { if(!r[x][y]) r[x][y]=1,s.push((QK){x,y}); } void spfa(int x) { dis[x][0]=0; r[x][0]=1; s.push((QK){x,0}); while(!s.empty()) { int dx=s.top().xi,miao=s.top().ci,del; s.pop(); if(miao==0) { if(hd[dx]&&dis[dx][1]>dis[dx][0]+sa[dx]) dis[dx][1]=dis[dx][0]+sa[dx],rd(dx,1); if(!hd[dx]&&dis[dx][1]>dis[dx][0]) dis[dx][1]=dis[dx][0],rd(dx,1); for(int i=h[dx];i!=-1;i=b[i].ne) { del=abs(w[dx]-w[b[i].v]); if((hd[dx]&&hd[b[i].v])||(!hd[dx]&&!hd[b[i].v])) if(dis[b[i].v][1]>dis[dx][0]+b[i].w) dis[b[i].v][1]=dis[dx][0]+b[i].w,rd(b[i].v,1); if(hd[dx]&&!hd[b[i].v]) if(dis[b[i].v][1]>dis[dx][0]+b[i].w+del) dis[b[i].v][1]=dis[dx][0]+b[i].w+del,rd(b[i].v,1); del=b[i].w-del; if(del<0) del=0; if(!hd[dx]&&hd[b[i].v]) if(dis[b[i].v][1]>dis[dx][0]+del) dis[b[i].v][1]=dis[dx][0]+del,rd(b[i].v,1); } } if(miao==1) { if(!hd[dx]&&dis[dx][0]>dis[dx][1]+sa[dx]) dis[dx][0]=dis[dx][1]+sa[dx],rd(dx,0); if(hd[dx]&&dis[dx][0]>dis[dx][1]) dis[dx][0]=dis[dx][1],rd(dx,0); for(int i=h[dx];i!=-1;i=b[i].ne) { del=abs(w[dx]-w[b[i].v]); if((hd[dx]&&hd[b[i].v])||(!hd[dx]&&!hd[b[i].v])) if(dis[b[i].v][0]>dis[dx][1]+b[i].w) dis[b[i].v][0]=dis[dx][1]+b[i].w,rd(b[i].v,0); if(!hd[dx]&&hd[b[i].v]) if(dis[b[i].v][0]>dis[dx][1]+b[i].w+del) dis[b[i].v][0]=dis[dx][1]+b[i].w+del,rd(b[i].v,0); del=b[i].w-del; if(del<0) del=0; if(hd[dx]&&!hd[b[i].v]) if(dis[b[i].v][0]>dis[dx][1]+del) dis[b[i].v][0]=dis[dx][1]+del,rd(b[i].v,0); } } r[dx][miao]=0; } } int main() { //freopen("t.txt","r",stdin); freopen("suika.in","r",stdin); freopen("suika.out","w",stdout); init(); spfa(1); if(dis[n][0]<dis[n][1]) printf("%d",dis[n][0]); else printf("%d",dis[n][1]); //while(1); return 0; }