dij

package 算法提高课; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class acw1129 { static class PII implements C ......

package 算法提高课; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class acw1128 { static int n, m; static int[] ......

package 算法提高课; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class acw1127 { static int n, p, c; static in ......

package 算法提高课; import java.util.Arrays; import java.util.Scanner; public class acw1126 { static int n, m; static int[][] g; static double[] d; static ......

思路就是，将每一条 $w_{i,j}$ 改为 $w_{i,j} + h_i - h_j$，这样每一条从 $s \rightarrow t$ 被影响的值都是 $h_s - h_t$，所以修改图上的最短路等于原图的最短路。 然后这个构造显然就是一个差分约束系统，但这样的话复杂度不是就又回来了。 但我们可 ......