题目连接：https://ac.nowcoder.com/acm/contest/904/D
第一次研究了一下这种题型，还是比较好理解的，因为有半价次数的限制，所以要把每一中情况都写出来，dp[现在的位置][次数]推到dp[到达的位置][次数]和dp[到达的位置][次数+1]这两种情况，然后跑一下最短路就可以了
AC代码：
#include<bits/stdc++.h> 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<b) return a; return b; } miao x[100010]; int head[100010]; ll dp[100010][15]; int vis[100010][15]; int cnt=0; void add(int a,int b,int c){ x[cnt].eend=b; x[cnt].weight=c; x[cnt].next=head[a]; head[a]=cnt++; } ll spfa(int start,int eend,int k){ queue<wang> 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 ",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(" "); // } ll ans=-1; for(int i=0;i<=k;i++){ // printf("+++%lld %d %d %lld ",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<n;i++){ int a,b; int c; scanf("%d %d %d",&a,&b,&c); add(a,b,c); } ll ans=spfa(1,m,k); printf("%lld ",ans); return 0; }