迷你滨

(1) 如果不使用魔法，显然是普通最短路算法。若当前路径长度 $$dp[u][0]+w(u,v)<dp[v][0]$$，那么更新 $$dp[v][0]=dp[u][0]+w(u,v)$$，表示不使用魔法的最小伤害。
(2) 使用魔法，有转移式：$$dp[v][j]=min(dp[v][j],dp[u][j-1])$$;
(3) 已经连续消除 $$k$$ 条边的伤害，正常转移：$$dp[v][k]=min(dp[v][k],dp[u][k]+w(u,v))$$;

```java
import java.io.*;
import java.util.*;
public class Main{
    static int maxn = 200005,n,m,inf=(int)1e9;
    static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
    static Scanner sc = new Scanner (System.in);
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
        int T = 1;
        while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    
    static class node{
    	int to;
    	int w;
    	public node(int a,int b) {
    		to=a;w=b;
    	}
    }
    static Vector<Vector<node>> g =new Vector<>();
    static int k=0;
    static int d[][] = new int [1001][11];
    static int cnt=0;
    
    static void dij() {
    	for(int i=0;i<n;i++)
    		for(int j=0;j<=k;j++) d[i][j] = inf;
    	d[0][0]=0;
    	Queue<int[]> q = new LinkedList<>();
    	q.add(new int[]{0,0});
    	while(!q.isEmpty()) {
    		int []p = q.poll();
    		int x=p[0],j=p[1];
    		for(node o:g.get(x)) {
    			int y = o.to,w = o.w;
    			if(j<k){
    			    if(d[y][j+1] > d[x][j]){
    			    d[y][j+1] = d[x][j];
    			    q.add(new int[]{y,j+1});
    			    }
    			}
    			if(j==0||j==k){
    		    	if(d[y][j] > d[x][j]+w){
    			    d[y][j] = d[x][j]+w;
    			    q.add(new int[]{y,j});
    		    	}
    			}
    		}
    	}
    }
    
    static void solve() throws IOException{
        n=I();k=I();m=I();
        for(int i=0;i<n;i++) g.add(new Vector<>());
        while(m-->0) {
        	int u=I(),v=I(),w=I();
        	g.get(u).add(new node(v,w));
        	g.get(v).add(new node(u,w));
        }
        dij();
        pw.println(Math.min(d[n-1][0], d[n-1][k]));
    }
}

```

0.0分

74 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

迷你滨

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

蓝桥杯2023年第十四届省赛真题-魔法阵(最短路+简单dp)

评论区

精彩推荐

计算质因子（C++代码）100以内质数直接打表就好了

字符串输入输出函数（Java代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

WU-链表数据求和操作（C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

蚂蚁感冒（C语言代码）

迷你滨