Uva(10269)(Adventure of Super Ma

链接：https://vjudge.net/problem/UVA-10269
思路：不得不说自己真的菜，不等号打反了看了大半个小时，这个题首先要用flyod预处理，中间有城堡的就不进行处理，保证处理后的最短路上都可以用魔法鞋，然后用dijstkra进行最短路，将d变二维进行dp即可，floyd预处理要学会！！！
代码：

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int INF = 1<<30;

int dp[101][11];
int t,a,b,l,m,k;

int G[105][105];

struct P{
int second, used;
    P(){}
    P(int s,int u):second(s),used(u){}
};

void dijstkra(){
    for(int i=0;i<a+b;i++){
        for(int j=0;j<=k;j++){
            dp[i][j] = INF;
        }
    }
    queue<P> qq;
    qq.push(P(a+b-1,k));
     dp[a+b-1][k] = 0;
    while(!qq.empty()){
        P p = qq.front();
        qq.pop();
        int u = p.second;
        int k1 = p.used;
        for(int v=0;v<a+b;v++){
            if(G[u][v]==INF||u==v)continue;
            //不用魔法鞋
               if(dp[v][k1]>dp[u][k1]+G[u][v]){
                dp[v][k1] = dp[u][k1] + G[u][v];
               qq.push(P(v,k1));
           }
          //满足条件用魔法鞋
               if(G[u][v]<=m&&k1>0&&dp[v][k1-1]>dp[u][k1]){
               dp[v][k1-1] = dp[u][k1];
               qq.push(P(v,k1-1));
           }
           }
        }
    }

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&a,&b,&l,&m,&k);

                for(int i=0;i<a+b;i++)
            for(int j=0;j<a+b;j++)G[i][j] = INF;

        for(int i=0;i<l;i++){
         int e,f,g;
         scanf("%d%d%d",&e,&f,&g);
         e--;
         f--;
         G[e][f] = G[f][e] = min(G[e][f],g);
        }

        for(int k=0;k<a;k++){
            for(int i=0;i<a+b;i++){
                for(int j=0;j<a+b;j++){
                    if(G[i][k]==INF||G[k][j]==INF)continue;
                G[i][j] = min(G[i][k]+G[k][j],G[i][j]);
                }
            }
        }
        dijstraka();
        int ans = INF;
        for(int i=0;i<=k;i++){
            ans = min(ans,dp[0][i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}