【题目描述】
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的路线。
/* 把一个洞拆成黑白两个洞，然后建图 注意虫洞跨越时的颜色是相对于同一时刻而言的 */ #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const int maxn = 30500; const ll inf = 987654321234LL; inline int read(){ char ch=getchar(); int f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}; while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}; return x*f; } struct edge{ int v; int w; int nxt; }e[maxn*6]; int n,m; int cnt,head[maxn],col[maxn],w[maxn],s[maxn]; ll dis[maxn],ans; bool vis[maxn]; void ins(int u,int v,int w){ cnt++; e[cnt].v = v; e[cnt].w = w; e[cnt].nxt = head[u]; head[u] = cnt; } void spfa(int st){ for(int i = 1;i <= n+n;i++) dis[i] = inf; dis[st] = 0; queue<int> q; int now,to; q.push(st); vis[st] = true; while(!q.empty()){ now = q.front(); q.pop(); for(int i = head[now];i;i = e[i].nxt){ to = e[i].v; if(dis[to] > dis[now] + e[i].w){ dis[to] = dis[now] + e[i].w; if(!vis[to]){ vis[to] = true; q.push(to); } } } vis[now] = false; } ans = min(dis[n],dis[n+n]); cout<<ans; } int main(){ freopen("holes.in","r",stdin); freopen("holes.out","w",stdout); n = read(); m = read(); for(int i = 1;i <= n;i++) col[i] = read(); for(int i = 1;i <= n;i++) w[i] = read(); for(int i = 1;i <= n;i++) s[i] = read(); int u,v,k,neww; for(int i = 1;i <= m;i++){ u = read(); v = read(); k = read(); if(col[u] == col[v]){ neww = k; ins(u,v+n,neww); ins(u+n,v,neww); }else{ neww = k + abs(w[u]-w[v]); ins(u+n,v+n,neww); neww = max(0,k - abs(w[u]-w[v])); ins(u,v,neww); } } for(int i = 1;i <= n;i++){ ins(i,i+n,0); ins(i+n,i,s[i]); } if(col[1])spfa(1+n); else spfa(1); return 0; }