题目连接：

　　第一次研究了一下这种题型，还是比较好理解的，因为有半价次数的限制，所以要把每一中情况都写出来，dp[现在的位置][次数]推到dp[到达的位置][次数]和dp[到达的位置][次数+1]这两种情况，然后跑一下最短路就可以了

　　AC代码：

#include
     
      using namespace std;typedef long long ll;typedef struct W_W{    int eend;    int weight;    int next;}miao;typedef struct W_w{    int eend;    int ci;}wang;ll minn(ll a,ll b){    if(a
      
        q1;    q1.push({
    1,0});    dp[1][0]=0;    while(q1.size()){        int dang=q1.front().eend;        int ci=q1.front().ci;        //printf("+++%d %d %lld \n",dang,ci,dp[dang][ci]);        q1.pop();        vis[dang][ci]=0;        for(int i=head[dang];i!=-1;i=x[i].next){            int to=x[i].eend;            if(dp[to][ci]==-1){                dp[to][ci]=dp[dang][ci]+x[i].weight;                if(vis[to][ci]==0){                    q1.push({to,ci});                    vis[to][ci]=1;                }            }            else{                if(dp[to][ci]>dp[dang][ci]+x[i].weight){                    dp[to][ci]=dp[dang][ci]+x[i].weight;                    if(vis[to][ci]==0){                        q1.push({to,ci});                        vis[to][ci]=1;                    }                }            }            if(ci+1<=k){                if(dp[to][ci+1]==-1){                    dp[to][ci+1]=dp[dang][ci]+x[i].weight/2;                    if(vis[to][ci+1]==0){                        q1.push({to,ci+1});                        vis[to][ci+1]=1;                    }                }                else{                    if(dp[to][ci+1]>dp[dang][ci]+x[i].weight/2){                        dp[to][ci+1]=dp[dang][ci]+x[i].weight/2;                        if(vis[to][ci+1]==0){                            q1.push({to,ci+1});                            vis[to][ci+1]=1;                        }                    }                }            }        }    }//    for(int i=1;i<=eend;i++){//        for(int j=0;j<=k;j++){//            printf("(%d %d) %lld ",i,j,dp[i][j]);//        }//        printf("\n");//    }    ll ans=-1;    for(int i=0;i<=k;i++){       // printf("+++%lld %d %d %lld\n",ans,eend,i,dp[eend][i]);        if(dp[eend][i]!=-1){            if(ans==-1){                ans=dp[eend][i];            }            else{                ans=minn(dp[eend][i],ans);            }        }    }    return ans;}int main(){    int m,n,k;    scanf("%d %d %d",&m,&n,&k);    memset(head,-1,sizeof(head));    memset(dp,-1,sizeof(dp));    memset(vis,0,sizeof(vis));    for(int i=0;i