NOIP模拟赛虫洞

【题目描述】

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的路线。

一开始数组设小了，WA了两个点，起码得设4倍以上

题解：

将每个虫洞拆分为一个白洞（i）和一个黑洞（i+n），然后以此建图，最后按照SPFA敲模板就行了

 1 #define REP(i,j,k) for(int i=j;i<=k;i++)
 2 
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<queue>
 7 using namespace std;
 8 
 9 const int MAXN=5001*2;
10 const int INF=0x7f7f7f7f;
11 
12 struct Edge
13 {
14     int to,w,next;
15 }E[200000];
16 int node=0,head[MAXN];
17 
18 int n,m;
19 int w[MAXN],p[MAXN];
20 
21 void insert(int u,int v,int w)
22 {
23     E[++node]=(Edge){v,w,head[u]};
24     head[u]=node;
25 }
26 
27 int spfa()
28 {
29     int dist[MAXN];
30     bool vis[MAXN];
31     memset(dist,0x7f,sizeof(dist));
32     memset(vis,0,sizeof(vis));
33     queue<int> Q;
34     int x=p[1]*n+1;
35     Q.push(x);dist[x]=0;vis[x]=1;
36     while(!Q.empty())
37     {
38         int q=Q.front();Q.pop();
39         for(int i=head[q];i;i=E[i].next)
40         {
41             if(dist[E[i].to]>dist[q]+E[i].w)
42             {
43                 dist[E[i].to]=dist[q]+E[i].w;
44                 if(!vis[E[i].to])
45                 {
46                     Q.push(E[i].to);
47                     vis[E[i].to]=1;
48                 }
49             }
50         }
51         vis[q]=0;
52     }
53     return min(dist[n],dist[n+n]);
54 }
55 
56 int main()
57 {
58     int t;
59     scanf("%d %d",&n,&m);
60     REP(i,1,n) scanf("%d",&p[i]);
61     REP(i,1,n) scanf("%d",&w[i]);
62     REP(i,1,n)
63     {
64         scanf("%d",&t);
65         insert(i,i+n,0);//白洞到黑洞不需要消耗燃料（我一开始没注意到。。。浪费了半个小时
66         insert(i+n,i,t);//黑洞到白洞消耗s[i]燃料
67     }
68     REP(i,1,m)
69     {
70         int u,v,k;
71         scanf("%d %d %d",&u,&v,&k);
72         t=abs(w[u]-w[v]);
73         if(p[u]==p[v])
74         {
75             insert(u,v+n,k);//u白洞跳到v点白洞时v为黑洞，所以是u到v+n
76             insert(u+n,v,k);//u黑洞跳到v点黑洞时v为白洞，所以是u+n到v
77         }
78         else
79         {
80             insert(u,v,k-t>0?k-t:0);//u白洞跳到v点黑洞时v为白洞，所以是u到v
81             insert(u+n,v+n,k+t);//u黑洞跳到v点白洞时，v为黑洞，所以是u+n到v+n
82         }
83     }
84     cout<<spfa();
85     return 0;
86 }

NOIP模拟赛 虫洞

NOIP模拟赛虫洞