虫洞
【题目描述】
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的路线。
试题分析：其余的不怎么难，难点就在于如何使黑洞变成白洞或者黑洞走到白洞一类复杂的东西。
其实只要细细思考一下，这道题还是不那么难的。
对于每一个"洞"，我们不知道它是那种洞，所以我们干脆将这个洞分成一白一黑两个洞。
设i为白洞，i+N为黑洞，那么我们需要这样建图：
①将第i个点的黑洞白洞连起来(在这个洞等一时刻)
②将这些点按照给定的输入连起来，注意它的另外一种洞也要与对面的另外一种洞连起来。
然后对于这样的一个图来说，我们只需要跑最短路就可以了，注意最后只要在编号为N的洞就好，不关心它是哪一个洞。
所以要取min(dis[end],dis[end+N])//编号为end的洞是黑洞或者白洞。
还有一个要注意的就是col[1]是黑洞我们要从1+N做，否则从1做
IQ掉线了将col[1]==1写成了col[1]==0 调了10分钟 QAQ
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
//#include<cmath> using namespace std;
const int INF = 9999999;
#define LL long long inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int N,M;
bool col[200001];//1黑 0白
int w[200001],s[200001];
int Node[1000000],Cost[1000000],Root[1000000],Next[1000000];
int dis[200001];bool inq[200001];
int que[1000001];
int cnt=0; void addedge(int u,int v,int w){
cnt++;
Node[cnt]=v;
Cost[cnt]=w;
Next[cnt]=Root[u];
Root[u]=cnt;
}
int SPFA(int s,int t){
if(col[s]==1) s=N+1;
memset(dis,INF,sizeof(dis));
memset(inq,false,sizeof(inq));
dis[s]=0,inq[s]=true;
int tail=0; que[++tail]=s;
for(int head=1;head<=tail;head++){
for(int x=Root[que[head]];x;x=Next[x]){
if(dis[Node[x]]>dis[que[head]]+Cost[x]){
dis[Node[x]]=dis[que[head]]+Cost[x];
if(!inq[Node[x]]){
inq[Node[x]]=true;
que[++tail]=Node[x];
}
}
}
inq[que[head]]=false;
}
return min(dis[t],dis[t+N]);
} int main(){
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();
}
for(int i=1;i<=M;i++){
int u=read(),v=read(),k=read();
if(col[u]==col[v]){
addedge(u,v+N,k);
addedge(u+N,v,k);
}
else{
int tmp=abs(w[u]-w[v]);
addedge(u+N,v+N,k+tmp);
addedge(u,v,max(k-tmp,0));
}
}
for(int i=1;i<=N;i++){
addedge(i,i+N,0);
addedge(i+N,i,s[i]);
}
printf("%d\n",SPFA(1,N));
return 0;
}