UVA 10269 Super Mario，最短路+動態規劃

這個題目我昨晚看到的，沒什么思路，因為馬里奧有boot加速器，只要中間沒有城堡，即可不耗時間和腳力，瞬間移動不超過L距離，遇見城堡就要停下來，當然不能該使用超過K次。。。我糾結了很久，最終覺得還是只能寫個BFS，剪了下枝，不出意料還是TLE。。。

后來還是找的別人博客看了一下。。。其實之前也做了好多DP，也應該能想到，既然加速器可以用k次，則，每個點都有k個狀態，通過DP，把各個狀態進行下取優，就可以了。。。

這不得不讓我對DP有了些新的理解，DP在狀態轉移的時候，就好像最短路里面的松弛操作，或者二者只是外表的不同，本質是遵循一個道理。

當然在DP之前還需要一些處理

首先用個g[][]二維數組把題目所給的路徑給存下來，再用Floyd把點到點的最短路先求出來，當然不是完全的Floyd，因為這個floyd求出來的最短路完全是為了之后用加速器，加速器不允許途中有城堡，因此在floyd的時候要加判斷條件，有城堡在中間就不走。

用一個d[i][k]表示i點在加速器使用了k次的最短路徑。

一開始還以為是總加速距離不能超過L，后來發現原來是每次。要細心

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 110
#define INF 1<<29
using namespace std;
int A,B,M,L,K;
int g[N][N],d[N][15];
int q[N*20],st[N*20],inq[N][20];
void init()
{for (int i=0;i<=A+B;i++){for (int j=0;j<=A+B;j++){if (i==j){g[i][j]=0;}elseg[i][j]=INF;}}
}
void floyd()
{int i,j,k;for (k=1;k<=A+B;k++){for (i=1;i<=A+B;i++){for (j=1;j<=A+B;j++){if (k>A) continue;//Floyd 只求能用加速器飛越的最短路if (g[i][j]>g[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j];//cout<<g[i][j]<<" "<<i<<" "<<j<<endl;
            }}}
}
void solve()
{int maxn=(K+1)*(A+B);int front=0,rear=0;memset(inq,0,sizeof inq);for (int i=1;i<=A+B;i++){for (int j=0;j<=K;j++){d[i][j]=INF;//cout<<d[i][j]<<endl;
        }}d[A+B][0]=0; //初始狀態q[rear]=A+B; //這次嘗試了一下手動隊列，而不是STL隊列，效果相同，不過手工的隊列時間應該好一些。st[rear]=0;rear++;while (front!=rear){int u=q[front];int k=st[front];front++;if (front>maxn)front=0;inq[u][k]=0;// cout<<u<<" "<<k<<" "<<d[u][k]<<endl;for (int i=1;i<=A+B;i++){if (d[i][k]>d[u][k]+g[u][i]) //進行普通最短路，保存當前狀態{d[i][k]=d[u][k]+g[u][i];if (!inq[i][k]){q[rear]=i;st[rear]=k;rear++;if (rear>maxn)rear=0;inq[i][k]=1;}}if (g[u][i]<=L && k<K && d[u][k]<d[i][k+1]) //如果能夠進行加速，并且加速后能更新加速后的狀態，則加速，并且保存該狀態。{d[i][k+1]=d[u][k];if (!inq[i][k+1]){inq[i][k+1]=1;q[rear]=i;st[rear]=k+1;rear++;if (rear>maxn)rear=0;}}}}
}
int main()
{int t;scanf("%d",&t);while (t--){scanf("%d%d%d%d%d",&A,&B,&M,&L,&K);init();for (int i=1;i<=M;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b]=g[b][a]=c;}floyd();solve();int ans=INF;for (int i=0;i<=K;i++)if (ans>d[1][i])ans=d[1][i];printf("%d\n",ans);}return 0;
}

其實整個動規過程就是最短路的松弛過程，尤其是它把每個點的狀態都求到了，并且把松弛成功（或者說狀態轉移成功）的點又存貯進了隊列，以它來繼續尋求更新其他點，這種思想應該可以再用到以后其他的DP問題中