生产（production）

【题目描述】

工厂为了生产一种复杂的产品，给各个生产部门制定了详细的生产计划。那么，就经常会有生产部门要把产品送到另一个生产部门作为原料。这是一个注重产品质量的工厂，所以每当有产品要从A部门运到B部门时，都要先从A部门送到质量检验处，检验合格后再从质量检验处运到B部门。

有些部门之间有传送带连接，厂长想知道每次将产品从一个部门运送到另一个部门最少需要多长时间。

【输入格式】

第一行两个整数n、m，n表示部门数量，m表示传送带数量。出于方便，1号部门是质量检验处。

接下来m行，每行三个整数u、v、w，表示有一条从u部门到v部门的传送带，传送过去需要w个单位时间。注意传送带是单向的。

接下来一个整数q，表示有q次运送。

接下来q行，每行两个数a、b，表示这一次要将产品从a部门运送到b部门。

【输出格式】

输出q行，每行一个整数，表示这次运送最少需要的时间。若没有传送方案，输出-1。

【样例输入】

5 5

1 2 3

1 3 5

4 1 7

5 4 1

5 3 1

4 2

5 3

2 3

【样例输出】

-1

【数据规模与约定】

30%的数据，n≤100，m≤500，w=1

60%的数据，n≤100，m≤5000

另20%的数据，q=1

100%的数据，2≤n≤3000，m≤100000，2≤a,b≤n，

q≤100000，1≤u,v≤n，1≤w≤10000

有些部门之间可能有多条传送带。

工厂的员工都非常尽职尽责，他们的认真和热情决定了产品的完美，所以不必考虑产品不合格的情况。

分别以1为起点和以1为终点跑一边最短路。

我是用的点。

题解是用的边。

大概敲了半个小时。

代码实现：

mine：

 #include<cstdio>

 #include<iostream>

 #define inf 30000010

 using namespace std;

 int n,m,q;

 int map[][],v[],w[];

 int a,b,c,pa,pb,na,nb;

 bool vv[],ww[];

 int main(){

     freopen("production.in","r",stdin);

     freopen("production.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

     if(i!=j) map[i][j]=inf;

     for(int i=;i<m;i++){

         scanf("%d%d%d",&a,&b,&c);

         map[a][b]=min(map[a][b],c);

     }

     for(int i=;i<=n;i++) v[i]=w[i]=inf;

     a=b=;vv[]=ww[]=;

     for(int k=;k<n;k++){

         pa=pb=inf;na=nb=;

         if(a) for(int i=;i<=n;i++){

             v[i]=min(v[i],v[a]+map[a][i]);

             if(!vv[i]&&v[i]<pa){pa=v[i];na=i;}

         }

         if(b) for(int i=;i<=n;i++){

             w[i]=min(w[i],w[b]+map[i][b]);

             if(!ww[i]&&w[i]<pb){pb=w[i];nb=i;}

         }

         vv[na]=ww[nb]=;a=na;b=nb;

     }

     scanf("%d",&q);

     for(int i=;i<=q;i++){

         scanf("%d%d",&a,&b);

         if(v[b]==inf||w[a]==inf) printf("-1\n");

         else printf("%d\n",v[b]+w[a]);

     }

     return ;

 }

std：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = ;

 const int M = ;

 const int inf = ;

 int n,m,q;

 struct Edge

 {

     int u,v,w;

 }xu[M];

 int point[N],to[M],next[M],val[M];

 int dui[N],mina[N],minb[N],top,tail;

 bool indui[N];

 void MakeMinLen(int x[])

 {

     int i;

     dui[]=;

     top=;tail=;

     indui[]=;

     for(i=;i<=n;i++)

         x[i]=inf;

     x[]=;

     while(top^tail)

     {

         top++;

         if(top==N)

             top=;

         int now=dui[top];

         int then=point[now];

         indui[now]=;

         while(then)

         {

             int tox=to[then];

             if(x[tox]>x[now]+val[then])

             {

                 x[tox]=x[now]+val[then];

                 if(!indui[tox])

                 {

                     indui[tox]=;

                     tail++;

                     if(tail==N)

                         tail=;

                     dui[tail]=tox;

                 }

             }

             then=next[then];

         }

     }

 }

 void InitGraph()

 {

     int i;

     scanf("%d%d",&n,&m);

     for(i=;i<=m;i++)

         scanf("%d%d%d",&xu[i].u,&xu[i].v,&xu[i].w);

     memset(point,,sizeof point);

     for(i=;i<=m;i++)

     {

         next[i]=point[xu[i].v];

         point[xu[i].v]=i;

         to[i]=xu[i].u;

         val[i]=xu[i].w;

     }

     MakeMinLen(mina);

     memset(point,,sizeof point);

     for(i=;i<=m;i++)

     {

         next[i]=point[xu[i].u];

         point[xu[i].u]=i;

         to[i]=xu[i].v;

         val[i]=xu[i].w;

     }

     MakeMinLen(minb);

 }

 void MakeAns()

 {

     scanf("%d",&q);

     while(q--)

     {

         int a,b;

         scanf("%d%d",&a,&b);

         int res=mina[a]+minb[b];

         if(res>=inf)

             res=-;

         printf("%d\n",res);

     }

 }

 int main()

 {

     freopen("production.in","r",stdin);

     freopen("production.out","w",stdout);

     InitGraph();

     MakeAns();

     return ;

 }

其实，如果卡空间的话，我会MLE的。

巴特西

生产（production）

最新文章

热门文章