[noip模拟赛]虫洞holes<SPFA>

虫洞(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

【设计思路】：

将这一个点为n的图变成一个大小为2*n的图，将每一个洞都拆为白洞和黑洞，建成两个图，分别为前1--n和后n+1--2*n

　　算了还是上代码看容易理解一点

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<vector>
  8 #define ll long long
  9 #define maxn 30005
 10 using namespace std;
 11 
 12 struct edge
 13 {
 14     int u,v,w,nxt;
 15 }e[maxn*10];
 16 
 17 int n,m;
 18 int pos=1,head[maxn],val[maxn],mvp[maxn],s[maxn],vis[maxn];
 19 //val表示当前i的初始状态
 20 //mvp表示当前i的质量
 21 //s表示自己到自己 
 22 //dis表示到出发点的消耗 
 23 int  dis[maxn];
 24 
 25 void add(int u,int v,int w)
 26 {
 27     e[pos].u=u;
 28     e[pos].v=v;
 29     e[pos].w=w;
 30     e[pos].nxt=head[u];
 31     head[u]=pos++;
 32 }
 33 
 34 int spfa(int f)
 35 {
 36     int ans;
 37     for(int i=1;i<=2*n;i++)
 38     {
 39         dis[i]=0x3f3f3f3f;//我在这卡了半天，打的时候直接背的模版
 40         //但是这道题自己是可以到自己这个点
 41         vis[i]=i==0?1:0;
 42     }
 43     dis[f]=0;
 44     queue<int>q;
 45     q.push(f);
 46     vis[f]=true;
 47     while(!q.empty())
 48     {
 49         int u=q.front();
 50         q.pop();
 51         for(int i=head[u];i>0;i=e[i].nxt)
 52         {
 53             int v=e[i].v;
 54             if(dis[v]>dis[u]+e[i].w)
 55             {
 56                 dis[v]=dis[u]+e[i].w;
 57                 if(!vis[v])
 58                 {
 59                     vis[v]=1;
 60                     q.push(v);
 61                 }
 62             }
 63         }
 64         vis[u]=0;
 65     }
 66     ans=min(dis[n],dis[2*n]);
 67     return ans;
 68     
 69 }
 70 
 71 
 72 
 73 void read()
 74 {
 75     
 76     
 77     scanf("%d%d",&n,&m);
 78     for(int i=1;i<=n;i++)
 79     {
 80         scanf("%d",&val[i]);
 81     }
 82     for(int i=1;i<=n;i++)
 83     {
 84         scanf("%d",&mvp[i]);
 85     }
 86     for(int i=1;i<=n;i++)
 87     {
 88         scanf("%d",&s[i]);
 89     }
 90     
 91     int a,b,c,num;
 92     
 93     for(int i=1;i<=m;i++)
 94     {
 95         scanf("%d%d%d",&a,&b,&c);
 96         if(val[a]==val[b])//洞的种类相同 
 97         {
 98             num=c;
 99             add(a,b+n,num);
100             add(a+n,b,num);//颜色相同两种图的路程一样 
101         }else
102         {//一黑一白 
103             int dw=abs(mvp[a]-mvp[b]);
104             
105             num=c+dw;
106             add(a+n,b+n,num);//黑走白 
107             
108             num=max(0,c-dw);//白走黑 
109             add(a,b,num);
110         }
111     }
112     
113     
114 }
115 
116 int main(){
117     freopen("holes.in","r",stdin);
118     freopen("holes.out","w",stdout);
119 
120     read();
121     
122     //*2是为了让两种状态图合二为一，不然要写两个spfa 
123     for(int i=1;i<=n;i++)
124     {
125         add(i,i+n,0);    //停留时为白 
126         add(i+n,i,s[i]);//停留时为黑 
127     }//自己与自己相连 
128     
129     if(val[1])//黑白洞讨论，不同时间的状态用不同的图 
130     {
131         printf("%d",spfa(n+1));
132     }
133     else
134     {
135         printf("%d",spfa(1));
136     }
137     
138     
139 }