1

我正在查看一些旧的竞赛问题，我发现了这个，它看起来很有趣，http ://dwite.ca/old/Problem5Jan2006.pdf，我尝试使用 floyd warshall 算法来获得从任何节点到任何节点的最短路径其他节点，你们能看到我做错了什么吗？它没有给出竞赛问题页面上列出的所需输出

import java.io.*;
import java.util.*;

public class DistanceBetween {


public static void main(String[] args) throws FileNotFoundException {
    Scanner s = new Scanner(new File("DATA5.txt"));
    int n = Integer.parseInt(s.nextLine());
    int[][] dist = new int[60][60];
    for(int y=0;y<60;++y)for(int x=0;x<60;++x)dist[y][x]=10000000;
    Map<Character, Integer> map = new TreeMap<Character, Integer>();
    for (int i = 0; i < n; ++i) {
        String text[] = s.nextLine().split(" ");
        int c = 0;
        if (!map.containsKey(text[0].charAt(0))) {
            map.put(text[0].charAt(0), c);
            c++;
        }
        if (!map.containsKey(text[0].charAt(1))) {
            map.put(text[0].charAt(1), c);
            c++;
        }
        dist[map.get(text[0].charAt(0))][map.get(text[0].charAt(1))] = Integer.parseInt(text[1]);
    }
    for (int k = 0; k < map.size(); ++k) {
        for (int i = 0; i < map.size(); ++i) {
            for (int j = 0; j < map.size(); ++j) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i = 0; i < 5; ++i) {
        String text = s.nextLine();
        System.out.println(dist[map.get(text.charAt(0))][map.get(text.charAt(1))]);
    }
}}
4

2 回答 2

2

您的代码中有几个问题：

覆盖映射

您int c是for循环的局部变量，这意味着使用的最高映射索引不会在下一次迭代中存活，因此下一次迭代中的读数会覆盖前一次。所以数据加载后距离矩阵没有正确填充。

解决方案：将int c = 0;外部从for循环中移开。

单向道路

说明中的道路是双向的，但您只能将它们注册为单向。因此，城镇之间不存在联系的情况会更高。

解决方案：dist[map.get(text[0].charAt(1))][map.get(text[0].charAt(0))] = Integer.parseInt(text[1]);在类似的后面添加。

除了这些难题之外，我还为您提供了一些提示。您没有关注它们，但如果您想提高您的编程技能，那么您应该考虑它们。

乱码

您的代码难以阅读，有多个重述信息，例如索引，解决过程是单一方法等。这样的代码不仅难以阅读，而且极难调试和修复。为了您自己的利益，我建议您将其写得更干净。

算法效率

Floyd-Warshall 的算法具有O(n^3)复杂性。问题的大小（城镇数量）是 AM = 13。在这种复杂性中，它会进行13^3 = 2197迭代。我知道，这似乎不是很多，但请考虑在给定时间限制内要解决的任务数量。

我建议您使用具有复杂性的 Dijkstra 算法O(|E| + |V|log|V|)。在这个任务中，经过一些简化的最坏情况是|E| = (|V|^2)/2, |V|=13。这意味着，最终的迭代次数是5 (|V|^2 / 2 + |V|log|V|) = 5 (13^2 / 2 + 13 * log13) ~ 5 * 132 = 660。如果我没有错并且犯了任何错误，那么这要少得多，尤其是当我们考虑任务总量时。

输入读数

我可能错了，但我参加了多个编程竞赛和竞赛，它从未强迫与会者处理文件。输入总是从文件重定向到标准输入。我想，这样做的主要原因是安全性，但简化可能也非常有益。

于 2013-03-21T08:51:07.840 回答
0

好吧，我得到了这个问题，我现在开始做 SPOJ，我得承认以后很难，但我遇到了同样的问题http://www.spoj.com/problems/SHPATH/，我也使用了弗洛伊德·沃歇尔

    import java.util.*;

    public class Floydwarshall {


public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    String q = s.nextLine();
    for(int t=0;t<Integer.parseInt(q);++t){
        int n = Integer.parseInt(s.nextLine());
        int[][] cost = new int[n][n];
        for (int y = 0; y < n; ++y) {
            for (int x = 0; x < n; ++x) {
                cost[x][y] = 10000;
            }
        }
        Map<String, Integer> map = new TreeMap<String, Integer>();
        int c = 0;
        for (int i = 0; i < n; ++i) {
            String a = s.nextLine();
            if (!map.containsKey(a)) {
                map.put(a, c);
                c++;
            }
            int f = Integer.parseInt(s.nextLine());
            for (int j = 0; j < f; ++j) {
                String text[] = s.nextLine().split(" ");
                cost[map.get(a)][Integer.parseInt(text[0]) - 1] =
                        cost[Integer.parseInt(text[0]) - 1][map.get(a)] = Integer.parseInt(text[1]);
            }
        }
        for (int k = 0; k < map.size(); ++k) {
            for (int i = 0; i < map.size(); ++i) {
                for (int j = 0; j < map.size(); ++j) {
                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
        int num = Integer.parseInt(s.nextLine());
        for (int i = 0; i < num; ++i) {
            String text[] = s.nextLine().split(" ");
            System.out.println(cost[map.get(text[0])][map.get(text[1])]);
        }
    }
}}

现在它对于示例输入运行正常，但是当我提交它时，它给了我这个

NZEC（非零退出代码） - 此消息意味着程序退出，返回一个不同于 0 的值到 shell。对于 C 等语言，这可能意味着您忘记在程序末尾添加“return 0”。对于解释型语言（包括 JAVA），NZEC 通常意味着您的程序崩溃或引发未捕获的异常。问题是我无法确定它在哪里崩溃或引发未捕获的异常，因为它
适用于示例输入

于 2013-03-21T21:08:02.480 回答