HDU 1385 Minimum Transport Cost

我的WA代码

我的大概思路就是，如果i->j，如果找到一个中间点k就直接简单的将path[i][j]=k，这样我们在遍历的时候就可以直接找到中间点k，然后通过一个递归的中序遍历的到i->k再到k->j这条路径。但是错了！！！

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Main {
    private final static int INF = 9999999;// flodyprivate final static int[][] flody(int[][] map, int[] city, int n) {
    int[][] path = new int[n+1][n+1];for(int i=1;i<=n;i++) {
    Arrays.fill(path[i], -1);}int tmp;for(int k=1;k<=n;k++) {
    for(int i=1;i<=n;i++) {
    if(map[i][k] == INF)continue;for(int j=1;j<=n;j++) {
    tmp = map[i][k] + map[k][j]+city[k];if(map[i][j] > tmp) {
    map[i][j] = tmp;path[i][j] = k;}else if(map[i][j] == tmp && path[i][j] > k) {
    path[i][j] = k;}}}}return path;}private final static void printFlody(int[][] path, int s, int e) {
    System.out.println(String.format("From %d to %d :", s, e));if(s == e) {
    System.out.println(String.format("Path: %d", s));return;}System.out.print(String.format("Path: %d-->", s));ArrayList<Integer> list = new ArrayList<>();middle(list, path, s, e);for(Integer u : list) {
    System.out.print(String.format("%d-->", u));}System.out.println(e);}private final static void middle(ArrayList<Integer> list, int[][] path, int i, int j) {
    int k = path[i][j];if(k == -1)return;middle(list, path, i, k);list.add(k);middle(list, path, k, j);}public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);int n;int[][] map;int[] city;int s, e;while(true) {
    n = sc.nextInt();if(n == 0) {
    break;}map = new int[n+1][n+1];for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
    map[i][j] = sc.nextInt();if(map[i][j] == -1)map[i][j] = INF;}}city = new int[n+1];for(int i=1;i<=n;i++) {
    city[i] = sc.nextInt();}int[][] flody = flody(map, city, n);while(true) {
    s = sc.nextInt();e = sc.nextInt();if(s == -1 && e == -1) {
    break;}printFlody(flody, s, e);System.out.println(String.format("Total cost : %d", map[s][e]));System.out.println();}}sc.close();}
}

AC的代码

于是最后AC的代码就改了一下，人家的思路是这样的！！！没太看的明白，不过语义上的理解就是：

1. 首先，如果有一条直通的边，就直接简单的将路径设置为“目的点”。
2. 如果遇到一个“中间点”，那么我们将记录i->j的“起始点”，这个起始点是path[k][j]。
3. 上面两条语义合起来看，就能够明白大致的意思：path[i][j]记录的是i->j的第一个节点
4. 假设i->j的第一个节点为k，那么接下来我们只需要知道k->j的路径了
5. 一直重复第4步操作，最后到k==j停止

import java.util.Scanner;public class Main {
    private final static int INF = 9999999;// flodyprivate final static int[][] flody(int[][] map, int[] city, int n) {
    int[][] path = new int[n+1][n+1];for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
    if(map[i][j] != INF) {
    path[i][j] = j;}}}int tmp;for(int k=1;k<=n;k++) {
    for(int i=1;i<=n;i++) {
    if(map[i][k] == INF)continue;for(int j=1;j<=n;j++) {
    tmp = map[i][k] + map[k][j]+city[k];if(map[i][j] > tmp) {
    map[i][j] = tmp;path[i][j] = path[i][k];}else if(map[i][j] == tmp && path[i][j] > path[i][k]) {
    path[i][j] = path[i][k];}}}}return path;}private final static void printFlody(int[][] path, int s, int e) {
    System.out.println(String.format("From %d to %d :", s, e));System.out.print(String.format("Path: %d", s));while(s!=e) {
    System.out.print(String.format("-->%d", path[s][e]));s = path[s][e];}System.out.println();}public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);int n;int[][] map;int[] city;int s, e;while(true) {
    n = sc.nextInt();if(n == 0) {
    break;}map = new int[n+1][n+1];for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
    map[i][j] = sc.nextInt();if(map[i][j] == -1)map[i][j] = INF;}}city = new int[n+1];for(int i=1;i<=n;i++) {
    city[i] = sc.nextInt();}int[][] flody = flody(map, city, n);while(true) {
    s = sc.nextInt();e = sc.nextInt();if(s == -1 && e == -1) {
    break;}printFlody(flody, s, e);System.out.println(String.format("Total cost : %d", map[s][e]));System.out.println();}}sc.close();}
}