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;
            }
            else
                g[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
",ans);
    }
    return 0;
}

其实整个动规过程就是最短路的松弛过程，尤其是它把每个点的状态都求到了，并且把松弛成功（或者说状态转移成功）的点又存贮进了队列，以它来继续寻求更新其他点，这种思想应该可以再用到以后其他的DP问题中

UVA 10269 Super Mario，最短路+动态规划

相关推荐