NOIP模拟赛 虫洞(holes)
Problem 3 虫洞(holes.cpp/c/pas)
【题目描述】
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的路线。
根据题意建图，跑一遍spfa完事
搞成2n个点，前n个白，后n个黑
对于u,v,k
颜色一样，add(u,v,k);add(u+n,v+n,k);
颜色不一样， add(u,v+n,k+);add(u+n,v,k-)
处理完后，自己的黑白两点相连
add(i,i+n,s[i]);add(i+n,i,0);
源点1，若白，spfa(1)
若黑，spfa(1+n)
ans=min(dist[n],dist[n*2])
我的程序怎么了呜呜呜调不出来
别人AC的程序
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#define ci const int &
using namespace std;
const int N=1000005;
int n,m;
int w[N],s[N],hole[N];
struct Ed{
int to,nxt,dis;
}ed[N];
int head[N],ednum;
void add(ci from,ci to,ci dis){
ed[++ednum].to=to;
ed[ednum].dis=dis;
ed[ednum].nxt=head[from];
head[from]=ednum;
}
int dis[N];
bool vis[N];
int inf=0x3f3f3f3f;
int spfa(int s,int t){
if(hole[s]==1)
s=n+1;
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
queue<int> q;
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].to;
if(dis[v]>dis[u]+ed[i].dis){
dis[v]=dis[u]+ed[i].dis;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
vis[u]=0;
}
return min(dis[t+n],dis[t]);
}
int main(){
freopen("holes.in","r",stdin);
freopen("holes.out","w",stdout);
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++){
int from,to,dis;
scanf("%d%d%d",&from,&to,&dis);
if(hole[from]==hole[to]){
add(from,to+n,dis);
add(from+n,to,dis);
}
else{
int tmp=abs(w[from]-w[to]);
add(from+n,to+n,dis+tmp);
add(from,to,max(dis-tmp,0));
}
}
for(int i=1;i<=n;i++){
add(i,i+n,0);
add(i+n,i,s[i]);
}
printf("%d
",spfa(1,n));
return 0;
}
我的程序
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n, m;
struct edge{
int from, to, next, k;
}ed[7001];//30000+30000+5000+5000
int first[1001], en;
void add(int u, int v, int k){
ed[++en].to = v;
ed[en].from = u;
ed[en].next = first[u];
ed[en].k = k;
first[u] = en;
}
bool inque[1001], dist[1001];
int co[501], w[501], s[501];
int spfa(int s){
if(co[s]) s+=n;
for(int i=1;i<=n*2;i++) dist[i]=1001;
// memset(inque, 0, sizeof(inque));
dist[s]=0;
queue<int>q;
q.push(s);
while(q.size()){
// cout << "&";
int now=q.front();q.pop();
inque[now]=false;
for(int i=first[now];i;i=ed[i].next){
int e=ed[i].to;
int d=dist[now]+ed[i].k;
// cout << e << " " << d << " " << dist[e] << endl;
if(dist[e] > d){
// cout << "*" << e << " " << dist[e] << endl;
dist[e]=d;
if(!inque[e]) inque[e]=true,q.push(e);
}
}
}
}
int u, v, k;
int ans;
int main()
{
cin >> n >> m;
for(int i=1;i<=2*n;i++) dist[i]=1010;
bool t;int delta;
for(int i=1;i<=n;i++){
cin >> co[i];
}
for(int i=1;i<=n;i++){
cin >> w[i];
}
for(int i=1;i<=n;i++){
cin >> s[i];
}
for(int i=1;i<=m;i++){
cin >> u >> v >> k;
delta = abs(w[u] - w[v]);
if(co[u]==co[v])
add(u, v, k),add(u + n, v + n, k);
else{
add(u, v + n,k + delta);//白->黑
add(u + n, v, max(0, k - delta));//黑->白
}
}
//1~n存白洞，n+1~n+n存黑洞
for(int i=1;i<=n;i++){
add(i+n,i,s[i]);//黑洞停留消耗燃料
add(i,i+n,0);//白洞停留不消耗燃料
}
/*
cout << en << endl;
for (int i=1;i<=n*2;i++){
cout<<i <<endl;
for(int e=first[i];e;e=ed[e].next) cout << "<" << ed[e].to << " " << ed[e].k << " ";
cout<< endl;
}*/
/*
for(int i=1;i<=en;i++){
cout << ed[i].from << "pay" << ed[i].k << "to" << ed[i].to <<endl;
}
*/
spfa(1);
/*
for (int i=1;i<=n;i++){
cout << dist[i] << " ";
}cout << endl;
ans = min(dist[n], dist[n*2]);
spfa(1+n);
if(min(dist[n], dist[n*2]) < ans)
*/ans = min(dist[n], dist[n*2]);
cout << ans << endl;
return 0;
}
/*
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
*/