首页 > 代码库 > 虫洞 (C++)
虫洞 (C++)
| 虫洞 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
|
试题描述
|
|
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<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
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;
}
const int maxn=10010;
const int maxm=1000010;
const int INF=1000000000;
struct Dijkstra {
int n,m,first[maxn],next[maxm];
struct Edge {int to,dist;}edges[maxm];
int done[maxn],d[maxn];
struct HeapNode {
int u,d;
bool operator < (const HeapNode& ths) const {return d>ths.d;}
};
void init(int n) {
this->n=n;m=0;
memset(first,0,sizeof(first));
}
void AddEdge(int u,int v,int w) {
//printf("%d --> %d %d\n",u,v,w);
edges[++m]=(Edge){v,w};next[m]=first[u];first[u]=m;
}
void solve(int s) {
rep(i,1,n) d[i]=INF,done[i]=0;
priority_queue<HeapNode> Q;
Q.push((HeapNode){s,0});d[s]=0;
while(!Q.empty()) {
int x=Q.top().u;Q.pop();
if(done[x]) continue;done[x]=1;
ren {
Edge& e=edges[i];
if(d[e.to]>d[x]+e.dist) {
d[e.to]=d[x]+e.dist;
Q.push((HeapNode){e.to,d[e.to]});
}
}
}
}
}sol;
//1---n 0 n+1----2*n 1
int n,m,type[maxn],w[maxn],s[maxn],u[maxn*3],v[maxn*3],k[maxn*3];
int first[maxn],next[maxn*3];
void Add(int x,int v) {
next[v]=first[x];first[x]=v;
}
int main() {
n=read();m=read();
rep(i,1,n) type[i]=read();
rep(i,1,n) w[i]=read();
rep(i,1,n) s[i]=read();
rep(i,1,m) u[i]=read(),v[i]=read(),k[i]=read(),Add(u[i],i);
sol.init(n*2);
rep(x,1,n*2) {
if(x<=n) sol.AddEdge(x,x+n,type[x]*s[x]);
else sol.AddEdge(x,x-n,(type[x-n]^1)*s[x-n]);
if(x<=n) ren {
if(type[x]==type[v[i]]) sol.AddEdge(x,v[i]+n,k[i]);
else if(type[x]) sol.AddEdge(x,v[i]+n,k[i]+abs(w[x]-w[v[i]]));
else sol.AddEdge(x,v[i]+n,max(0,k[i]-abs(w[x]-w[v[i]])));
}
else for(int i=first[x-n];i;i=next[i]) {
if(type[x-n]==type[v[i]]) sol.AddEdge(x,v[i],k[i]);
else if(type[x-n]) sol.AddEdge(x,v[i],max(0,k[i]-abs(w[x-n]-w[v[i]])));
else sol.AddEdge(x,v[i],k[i]+abs(w[x-n]-w[v[i]]));
}
}
sol.solve(1);
printf("%d\n",min(sol.d[n],sol.d[n*2]));
return 0;
}
虫洞 (C++)