2020牛客暑期多校训练营(第五场)A Portal 题解

题意:

n( n<=300 )个点m条边( m<=40000 )的带边权无向连通图,要求按顺序经过a1 b1 a2 b2 ……ak bk,( k<=300 )你有一个传送门,可以随时在脚下放置一个传送门,两个传送门之间可以相互传送,但场上最多同时存在两个传送门,你可以在任意时候关掉任意一个传送门。问走过这2k个点最短路程是多少。

当时第一反应是设f[x][y][z]为在ak点打算走到bk点,传送门在y z时的最短路程,但是发现时间复杂度不对。后来想到这张图可以做最小生成树简化成一个树,这样路径就好找多了。然后发现有这么一个美妙的性质:当场上有两个传送门时,当且仅当我们站在一个传送门所在点时这两个传送门对我们都有意义,否则只有一个传送门对我们有意义。

那么状态就可以简化了,我们设f[x][y]为在ak点,打算向bk点走,有一个传送门在y点时的最短路程,y=0 时说明场上还没有传送门。

接下来,我们枚举是否在ak走向bk的过程中放置传送门,以及以怎样的路径放置。bk到ak+1的过程同理。

2020牛客暑期多校训练营(第五场)A Portal 题解
  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<queue>
  5 #include<cmath>
  6 #include<cstring>
  7 #include<algorithm>
  8 #define N 305
  9 using namespace std;
 10 int n,m,zz,a[N],K;
 11 struct ro{
 12     int to,next,l;
 13 }road[N*N*2];
 14 void build(int x,int y,int z)
 15 {
 16     zz++;
 17     road[zz].to=y;
 18     road[zz].next=a[x];
 19     road[zz].l=z;
 20     a[x]=zz;
 21 }
 22 long long dis[N][N];
 23 queue<int > q1;
 24 bool rd[N];
 25 void spfa(int S)
 26 {
 27     memset(rd,0,sizeof(rd));
 28     rd[S]=1;q1.push(S);
 29     dis[S][S]=0;
 30     while(!q1.empty())
 31     {
 32         int x=q1.front();q1.pop();
 33         rd[x]=0;
 34         for(int i=a[x];i;i=road[i].next)
 35         {
 36             int y=road[i].to;
 37             if(dis[S][y]>dis[S][x]+road[i].l)
 38             {
 39                 dis[S][y]=dis[S][x]+road[i].l;
 40                 if(!rd[y])
 41                 {
 42                     rd[y]=1;
 43                     q1.push(y);
 44                 }
 45             }
 46         }
 47     }
 48 }
 49 int F[N][2];
 50 long long f[2][N];
 51 int main()
 52 {
 53     memset(dis,0x3f,sizeof(dis));
 54     scanf("%d%d%d",&n,&m,&K);
 55     for(int i=1;i<=m;i++)
 56     {
 57         int x,y,z;
 58         scanf("%d%d%d",&x,&y,&z);
 59         build(x,y,z);
 60         build(y,x,z);
 61     }
 62     for(int i=1;i<=n;i++)
 63     {
 64         spfa(i);
 65     }
 66     for(int i=1;i<=K;i++)
 67     {
 68         scanf("%d%d",&F[i][0],&F[i][1]);
 69     }
 70     int nw=1,la=0;
 71     long long mx;
 72     for(int j=0;j<=n;j++) f[0][j]=f[1][j]=1e15;
 73     mx=f[0][0];
 74     f[nw][0]=0;
 75     F[0][1]=1;
 76     for(int i=1;i<=K;i++)
 77     {
 78         nw^=1,la^=1;
 79         for(int j=0;j<=n;j++) f[nw][j]=1e15;
 80         int x=F[i-1][1],y=F[i][0];
 81         for(int j=0;j<=n;j++)
 82         {
 83             if(!j)
 84             {
 85                 f[nw][0]=min(f[nw][0],f[la][0]+dis[x][y]);
 86             }
 87             else
 88             {
 89                 f[nw][j]=min(f[nw][j],f[la][j]+dis[x][y]);
 90                 for(int k=0;k<=n;k++)
 91                 {
 92                     f[nw][j]=min(f[nw][j],f[la][k]+dis[x][j]+dis[j][y]);
 93                     f[nw][j]=min(f[nw][j],f[la][k]+dis[k][j]+dis[j][y]);
 94                     f[nw][j]=min(f[nw][j],f[la][k]+dis[k][j]+dis[k][y]);
 95                     f[nw][j]=min(f[nw][j],f[la][k]+dis[x][j]+dis[k][y]);
 96                 }
 97             }
 98         }
 99          
100         nw^=1,la^=1;
101         for(int j=0;j<=n;j++) f[nw][j]=1e15;
102         x=F[i][0],y=F[i][1];
103         for(int j=0;j<=n;j++)
104         {
105             if(!j)
106             {
107                 f[nw][0]=min(f[nw][0],f[la][0]+dis[x][y]);
108             }
109             else
110             {
111                 f[nw][j]=min(f[nw][j],f[la][j]+dis[x][y]);
112                 for(int k=0;k<=n;k++)
113                 {
114                     f[nw][j]=min(f[nw][j],f[la][k]+dis[x][j]+dis[j][y]);
115                     f[nw][j]=min(f[nw][j],f[la][k]+dis[k][j]+dis[j][y]);
116                     f[nw][j]=min(f[nw][j],f[la][k]+dis[k][j]+dis[k][y]);
117                     f[nw][j]=min(f[nw][j],f[la][k]+dis[x][j]+dis[k][y]);
118                 }
119             }
120         }
121     }
122     long long ans=mx;
123     for(int i=0;i<=n;i++)
124     {
125         ans=min(ans,f[nw][i]);
126     }
127     printf("%lld\n",ans);
128     return 0;
129 }
View Code

 

上一篇:第八次抽考(随机数)


下一篇:关于python3四舍五入的问题