1

私はいくつかの古いコンテストの質問を調べていましたが、これは楽しそうに見えました。http://dwite.ca/old/Problem5Jan2006.pdf、フロイドウォーシャルアルゴリズムを使用して、任意のノードから任意のノードへの最短経路を取得しようとしました。他のノード、あなたたちは私が間違ったことを見ることができますか？コンテストの質問ページに記載されている目的の出力が得られません

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反復が行われます。それほど多くはないように思われるかもしれませんが、特定の制限時間内に解決するタスクの量を考慮してください。

複雑なダイクストラのアルゴリズムを使用することをお勧めします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とは異なる値を返したことを意味します。Cなどの言語の場合、これはおそらく、プログラムの最後に「return0」を追加するのを忘れたことを意味します。インタプリタ言語（JAVAを含む）の場合、NZECは通常、プログラムがクラッシュしたか、キャッチされない例外が発生したことを意味します。
問題は、サンプル入力で動作するため、クラッシュしたり、キャッチされない例外が発生したりする場所を特定できないことです

于 2013-03-21T21:08:02.480 に答える