import java.util.Arrays; import java.util.Scanner; /*题目描写叙述: 有n个城市。城市间有m条道路。每条道路都有长度d。给你起点城市s终点终点t。要求输出起点到终点的最短距离 输入: 输入n,m。城市的编号是1~n,然后是m行。每行3个数 a,b,d,表示a城市和b城市之间有一条道路。且其长度为d。如果a与b之间若有道路。则仅仅 有一条道路。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。(1<n<=1000, 0<m<100000, s != t) 输出: 输出一行有一个数, 表示最短距离。 例子输入: 3 2 1 2 5 2 3 4 1 3 0 0 例子输出: 9*/ /* * 起点s,终点t * map[a][b]表示a点与b点直接连通的距离,没有直接连通则为无限大 * d[i]表示s点到i点的距离 * fa[i]表示i点是否已经更新过了最短距离,true表示没有被使用,false表示已经被使用 * * 大致步骤例如以下: * 1.先从d数组里找到一个离起点近期的点k,并且fa[k]必须为true,距离为d[k] * 2.将fa[k]赋值为false。接下来将用k来更新最短距离 * 3.随意一点j,且fa[j]为false。若d[k] + map[k][j]比d[j]小则将d[k] + map[k][j]赋值给d[j] * 换句话说就是先从起点走到k点(d[k])。再从k点走到j(map[k][j]),若比从起点 * 到j的距离(d[j])短。则d[j]应该变为d[k] + map[k][j] * 4.回到步骤1,直到全部fa数组里全部点都为false。 * 5.d[t]就是起点s到终点t的最短距离 */ public class Dijkstra { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int m = cin.nextInt(); while (n != 0 && m != 0) { int[][] map = new int[n + 5][n + 5]; for (int i = 0; i < map.length; i++) { // 将map随意两点的初值设置一个非常大的值,表示两点间的距离无限大,即没有通路 // 除以3是由于后面有加的地方,我害怕两个值加会超过Integer.MAX_VALUE Arrays.fill(map[i], Integer.MAX_VALUE / 3); } for (int i = 1; i <= m; i++) { int a = cin.nextInt(); int b = cin.nextInt(); int c = cin.nextInt(); // a点到b点的距离是c map[a][b] = c;// a到b的距离赋为c map[b][a] = c;// b到a的距离赋为c } int s = cin.nextInt();// 起点 int t = cin.nextInt();// 终点 // d数组:d[i]表示起点s到i点的最短距离 int[] d = new int[n + 5]; Arrays.fill(d, Integer.MAX_VALUE); // fa数组:fa[i]表示i点是否已经更新过了最短距离,true表示没有被使用,false表示已经被使用 boolean[] fa = new boolean[n + 5]; Arrays.fill(fa, true);// 初始值都为true,表示全部点都能够用 fa[s] = false;// 起点不能更新自己,所以为false for (int i = 1; i <= n; i++) { d[i] = map[s][i];// d[i]的为题目给出的map[s][i] } // 将全部点的fa的值都变为false,由于s点已经为false。所以我这里写i<n而不是i<=n for (int i = 1; i < n; i++) { int min = Integer.MAX_VALUE; int k = 0; for (int j = 1; j <= n; j++) { if (fa[j] && min > d[j]) { min = d[j];// 找到一个最小的d[j] k = j;// 并记录下标为k } } fa[k] = false;// 这样接下来就不会出现d[k] + map[k][k]的情况了,k点在i添加时被抛弃 for (int j = 1; j <= n; j++) { // if(j点可用 && 当前起点s到k的最短距离+k到j直接连通的距离<当前起点s到j的最短距离) if (fa[j] && d[k] + map[k][j] < d[j]) { d[j] = d[k] + map[k][j];// 找到了更优的s到j的最短距离 } } } System.out.println(d[t]);// 整个过程之后d[t]就是s到t的最短距离了 n = cin.nextInt(); m = cin.nextInt(); } } }
import java.util.Arrays; import java.util.Scanner; /*题目描写叙述和那道Dijkstra的题一样,只是这个时间复杂度是O(n^3), 假设和上一道题一样。n要是最多1000的话。这个算法就会超时 看完了这个算法能够看看九度1447。分别用这两种算法都做一下 这里有一篇别人写的博客能够參考一下:http://blog.csdn.net/jdplus/article/details/19816375 */ /* * 起点s。终点t * map[a][b]表示a点与b点直接连通的距离。没有直接连通则为无限大 * 这个代码非常easy大致思路: * 分别把全部节点都当做媒介节点 */ public class Floyd_warshall{ public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int m = cin.nextInt(); while (n != 0 && m != 0) { int[][] map = new int[n + 5][n + 5]; for (int i = 0; i < n + 5; i++){ //和Dijkstra的算法一样我害怕会超过范围就除以了3 Arrays.fill(map[i], Integer.MAX_VALUE / 3); } for (int i = 1; i <= m; i++) { int a = cin.nextInt(); int b = cin.nextInt(); int c = cin.nextInt(); map[a][b] = c; map[b][a] = c; } //这个代码非常easy,以下两段切割线之间就是最核心的代码 //---------------------------------- for (int k = 1; k <= n; k++)//k为媒介节点 for (int i = 1; i <= n; i++)//i为全部的起点 for (int j = 1; j <= n; j++)//j为全部的终点 /* * 以下是最关键的两句: * 假设i到k的距离加上k到j的距离比i到j的距离小, * 则更新map[i][j]为map[i][k] + map[k][j] * 就是不断把k当做中间节点来更新其它的两点的距离 */ if (map[i][k] + map[k][j] < map[i][j]) {//假设i到k的距离加上k到j的距离比i到j的距离小 map[i][j] = map[i][k] + map[k][j];//更新map[i][j] } //---------------------------------- int s = cin.nextInt(); int t = cin.nextInt(); System.out.println(map[s][t]);//更新后的map[s][t]已经是s到t的最短里的 n = cin.nextInt(); m = cin.nextInt(); } } }
九度1447能够两种方法都能够,九度1008仅仅能用第一种方法