飞飞侠

题目大意

首先考虑最简单的两种做法:直接按照题目模拟(建一个堆),或者直接暴力连边跑最短路,但是时间复杂度都是n^4,很显然通过不了这道题目

但是我们会惊奇的发现第一种做法的空间占用量极低,于是我们考虑一种常规的优化:记录各个状态。

我们定义f[i][j][k]代表目前停留在(i,j),在不弹射的条件下还能走k个点需要花费的最小费用

那么我们对于每一个点,只有五种走法:上,下,左,右,不动,也许你会问最后这一种是怎么回事,其实加入这一种状态的目的就是要让每一个点都有被考虑弹射的可能性,并且将最后的答案都汇聚到k=0的状态下,便于我们进行比较。

那么我们跑Dijkstra就行了,正确性比较显然:每一个点都有机会被考虑弹射,到达每一步时一定最优。

时间复杂度:O(n*m*(n+m))

最后附上本题代码:(自动省略头文件)

  1 struct node
  2 {
  3     LL px,py,nowcost,energy;
  4     bool operator < (const node &a) const
  5     {
  6         return nowcost > a.nowcost;
  7     }
  8 };
  9 LL dtx[5]= {0,1,0,-1,0},dty[5]= {1,0,-1,0,0};
 10 LL n,m;
 11 LL b[maxn+5][maxn+5],cost[maxn+5][maxn+5];
 12 LL x[4],y[4];
 13 LL f[maxn+5][maxn+5][maxn*2+5];
 14 bool vis[maxn+5][maxn+5][maxn*2+5];
 15 
 16 void dijkstra(int id)
 17 {
 18     for (int i = 1; i <= n; i++)
 19     {
 20         for (int j = 1; j <= m; j++)
 21         {
 22             for (int k = 0; k <= n + m; k++)
 23             {
 24                 vis[i][j][k] = 0;
 25                 f[i][j][k] = inf;
 26             }
 27         }
 28     }
 29     priority_queue<node>q;
 30     node temp; 
 31     temp.px=x[id],temp.py=y[id],temp.energy=b[x[id]][y[id]],temp.nowcost=cost[x[id]][y[id]];
 32     q.push(temp);
 33     vis[x[id]][y[id]][0]=1;
 34     f[x[id]][y[id]][b[x[id]][y[id]]]=cost[x[id]][y[id]];
 35     while(!q.empty())
 36     {
 37         if(vis[x[1]][y[1]][0]==1&&vis[x[2]][y[2]][0]==1&&vis[x[3]][y[3]][0]==1) return;
 38         node w=q.top();
 39         q.pop();
 40         LL tx=w.px,ty=w.py,k=w.energy;
 41         if(vis[tx][ty][k]==1) continue;
 42         vis[tx][ty][k]=1;
 43         if(k!=0)
 44         {
 45             for(int i=0; i<=4; i++)
 46             {
 47                 LL nxtx=tx+dtx[i],nxty=ty+dty[i];
 48                 if(nxtx>=1&&nxtx<=n&&nxty>=1&&nxty<=m)
 49                 {
 50                     if(f[nxtx][nxty][k-1]>f[tx][ty][k])
 51                     {
 52                         f[nxtx][nxty][k-1]=f[tx][ty][k];
 53                         node temp;
 54                         temp.px = nxtx;
 55                         temp.py = nxty;
 56                         temp.energy = k - 1;
 57                         temp.nowcost = f[nxtx][nxty][k - 1];
 58                         q.push(temp);
 59                     }
 60                 }
 61             }
 62         }
 63         else
 64         {
 65             if(f[tx][ty][0]+cost[tx][ty]<f[tx][ty][b[tx][ty]])
 66             {
 67                 f[tx][ty][b[tx][ty]]=f[tx][ty][0]+cost[tx][ty];
 68                 node temp;
 69                 temp.px = tx;
 70                 temp.py = ty;
 71                 temp.energy = b[tx][ty];
 72                 temp.nowcost = f[tx][ty][b[tx][ty]];
 73                 q.push(temp);
 74             }
 75         }
 76     }
 77 }
 78 int main()
 79 {
 80     scanf("%lld%lld",&n,&m);
 81     for(int i=1; i<=n; i++)
 82     {
 83         for(int j=1; j<=m; j++)
 84         {
 85             scanf("%lld",&b[i][j]);
 86             b[i][j] = min(b[i][j],1LL*(max(i - 1,(int)n-i) + max(j - 1,(int)m - j)));
 87         }
 88     }
 89     for(int i=1; i<=n; i++)
 90     {
 91         for(int j=1; j<=m; j++)
 92         {
 93             scanf("%lld",&cost[i][j]);
 94         }
 95     }
 96     for(int i=1; i<=3; i++) scanf("%lld%lld",&x[i],&y[i]);
 97     dijkstra(1);
 98     LL a1 = f[x[2]][y[2]][0],a2 = f[x[3]][y[3]][0];
 99     dijkstra(2);
100     LL b1 = f[x[1]][y[1]][0],b2 = f[x[3]][y[3]][0];
101     dijkstra(3);
102     LL c1 = f[x[1]][y[1]][0],c2 = f[x[2]][y[2]][0];
103     LL ans = inf;
104     char s;
105     if (b1 + c1 < ans)
106     {
107         ans = b1 + c1;
108         s = 'X';
109     }
110     if (a1 + c2 < ans)
111     {
112         ans = a1 + c2;
113         s = 'Y';
114     }
115     if (a2 + b2 < ans)
116     {
117         ans = a2 + b2;
118         s = 'Z';
119     }
120     if(ans>=inf) printf("NO\n");
121     else printf("%c\n%lld\n",s,ans);
122     return 0;
123 }

 

上一篇:FZU_2150_(BFS)


下一篇:迷宫问题 (bfs广度优先搜索记录路径)