【题目描述】：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 51 0 1 010 10 100 105 20 15 101 2 302 3 401 3 201 4 2003 4 200【样例输出】：130【时间限制、数据范围及描述】：时间：1s 空间：256M对于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的路线。本题可以开2*n个点,n个表示黑洞,另外n个表示白洞。建边时如果当前边所连接的两个洞为相同洞时,则直接建边,燃料值不变化,若两端为不同洞,则加上或减去两洞质量差。考虑到每过1单位时间黑洞变白洞,白洞变黑洞，那么可以由i向i+n建边,并且要考虑燃料变化。Code:#include#include #include #include #include #include #include #include using namespace std;const int N=1000005,INF=0x3f3f;int n,m;int w[N],s[N],hole[N];int to[N],Cost[N],head[N],next[N];int dis[N];bool vis[N];int cnt;void Push(int u,int v,int w1){ cnt++; to[cnt]=v; Cost[cnt]=w1; next[cnt]=head[u]; head[u]=cnt;}int SPFA(int s,int t){ if(hole[s]==1){ s=n+1; } memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); queue Q; dis[s]=0; vis[s]=true; Q.push(s); while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int i=head[u];i;i=next[i]){ int v=to[i]; if(dis[v]>dis[u]+Cost[i]){ dis[v]=dis[u]+Cost[i]; if(!vis[v]){ vis[v]=true; Q.push(v); } } } vis[u]=false; } return min(dis[t],dis[t+n]);}int main(){ int u,v,k; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&hole[i]); } for(int i=1;i<=n;i++){ scanf("%d",&w[i]); } for(int i=1;i<=n;i++){ scanf("%d",&s[i]); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&k); if(hole[u]==hole[v]){ Push(u,v+n,k); Push(u+n,v,k); } else{ int tmp=abs(w[u]-w[v]); Push(u+n,v+n,k+tmp); Push(u,v,max(k-tmp,0)); } } for(int i=1;i<=n;i++){ Push(i,i+n,0); Push(i+n,i,s[i]); } printf("%d\n",SPFA(1,n)); return 0;}