定义两个结构体：
struct Edge{ //存边,不解释
int from,to,val,next;
}edge[MX];
struct Sta{ //状态,到某位置时的花费
int arr,cos;
};
我们用一个二维数组 dis[i][j] 表示到 i 位置花费 j 个代价，同时以状态建队：queue<Sta> q;
用了 j 次法力到达 i -> 更新 -> 入队
判断 j < t（是否还可以施法）-> 更新 -> 入队
代码如下
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; int n,m,k,dis[101][101],first[101]; bool vis[101][101]; struct Edge{ int to,val,next; }edge[2002]; struct Sta{ int pos,cos; }; int cnt; void add(int from,int to,int val) { edge[++cnt].to=to; edge[cnt].val=val; edge[cnt].next=first[from]; first[from]=cnt; } void Spfa() { queue<Sta> q; memset(dis,0x3f,sizeof(dis)); dis[1][0]=0; vis[1][0]=1; q.push((Sta){1,0}); while(!q.empty()) { Sta cur=q.front();q.pop(); int pos=cur.pos; int cost=cur.cos; for(int i=first[pos];i;i=edge[i].next) { int to=edge[i].to; if(dis[pos][cost]+edge[i].val<dis[to][cost]) { dis[to][cost]=dis[pos][cost]+edge[i].val; if(!vis[to][cost]){ vis[to][cost]=1; q.push((Sta){to,cost}); } } } if(cost<k) { for(int i=first[pos];i;i=edge[i].next) { int to=edge[i].to; if(dis[pos][cost]+(edge[i].val>>1) < dis[to][cost+1]) { dis[to][cost+1]=dis[pos][cost]+(edge[i].val/2); if(!vis[to][cost+1]){ vis[to][cost+1]=1; q.push((Sta){to,cost+1}); } } } } } int ans=0x3f3f3f3f; for(int i=0;i<=k;++i) ans=min(ans,dis[n][i]); printf("%d",ans); } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;++i){ int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from,to,val); add(to,from,val); } Spfa(); return 0; }
原文：https://www.cnblogs.com/qseer/p/9389561.html