zoj 1232 adventure of super mario

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=1010;
const int inf=0x3f3f3f3f;
int fly[maxn][maxn];
int dp[maxn][maxn],d[maxn][maxn];

int a,b,l,n,m,K;

void ()
    {

        for (int k=1;k<=n;k++)
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    {
                        if(d[i][k]+d[k][j]<d[i][j])
                            {
                                d[i][j]=d[i][k]+d[k][j];
                                 if(k<=a && d[i][j]<=l)
                                    {
                                        fly[i][j]=fly[j][i]=1;
                                    }
                            }

                    }
    }


int main()
    {
        int T;
        scanf("%d",&T);
        while (T--)
            {
                scanf("%d%d%d%d%d",&a,&b,&m,&l,&K);
                n=a+b;
                memset(fly,0,sizeof(fly));
                memset(d,inf,sizeof(d));
                for(int i=1;i<=m;i++)
                    {
                        int a,b,c;
                        scanf("%d%d%d",&a,&b,&c);
                        d[a][b]=c;
                        d[b][a]=c;
                        if(c<=l)
                            {
                                fly[a][b]=fly[b][a]=1;
                            }
                    }
                floyd();

                memset(dp,inf,sizeof(dp));
                    for(int i=1;i<=n;i++)
                        {
                            dp[i][0]=d[1][i];
                        }
                    for(int k=0;k<=K;k++)
                        {
                            dp[1][k]=0;
                        }

                for (int i=2;i<=n;i++)
                    {
                        for(int k=1;k<=K;k++)
                            {
                                for (int j=1;j<=i;j++)
                                    {
                                        if(fly[i][j])//如果说当前的路可以用鞋子，就用
                                            dp[i][k]=min(dp[j][k-1],dp[i][k]);
                                        dp[i][k]=min(dp[i][k],dp[j][k]+d[j][i]);//没有用鞋子
                                    }

                            }
                    }

                printf("%dn",dp[n][K]);
            }
        return 0;
    }