虫洞
题目描述
N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。
从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。
从黑洞跃迁到白洞，消耗的燃料值增加delta。
路径两端均为黑洞或白洞，消耗的燃料值不变化。
作为压轴题，自然不会是如此简单的最短路问题，所以每过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
样例解释
按照1->3->4的路线。
数据范围与提示
对于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
解释
本题本来是要转化为最短路的，建图有些麻烦，考试的时候写暴力，无脑地堆优化BFS，189ms A掉了，与正解不相上下，864KB 内存远远领先正解......
本来觉得拿个60分算最好情况了，结果出人意料......附上原代码
补充一下：那个vis数组是为了让节点对结果贡献不超过两次，一次作为黑点一次作为白点，再多就重复无意义了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=5000+5,maxm=30000+5;
int n,m,zt[maxn],w[maxn],s[maxn],cnt,head[maxn];
int vis[maxn];
int x,time,cost;
struct Edge{int to,next,val;}e[maxm];
struct Node{
int now,time,cost;
Node(){}
Node(int a,int b,int c){
now=a,time=b,cost=c;
}
bool operator < (const Node &a)const{
return cost>a.cost;
}
};
priority_queue<Node> q;
void A(int x,int y,int z){
e[++cnt].to=y;
e[cnt].next=head[x];
e[cnt].val=z;
head[x]=cnt;
}
bool W(int x){
if((time+zt[x])%2==0)return 1;
else return 0;
}
int main(){
// freopen("1.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&zt[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,a,b,c;i<=m;++i){
scanf("%d%d%d",&a,&b,&c);
A(a,b,c);
}
q.push(Node(1,0,0));
while(!q.empty()){
x=q.top().now,time=q.top().time,cost=q.top().cost;q.pop();
if(x==n){
printf("%d
",cost);
return 0;
}
if(vis[x]>1)continue;
vis[x]++;
if(W(x))q.push(Node(x,time+1,cost));
else q.push(Node(x,time+1,cost+s[x]));
for(int i=head[x],y,co;i;i=e[i].next){
y=e[i].to;
if(W(x)&&!W(y)){
if(e[i].val-abs(w[x]-w[y])>=0)co=e[i].val-abs(w[x]-w[y]);
else co=0;
}
else if(!W(x)&&W(y))co=e[i].val+abs(w[x]-w[y]);
else co=e[i].val;
q.push(Node(y,time+1,cost+co));
}
}
return 0;
}