質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • Java

    15772questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

有向グラフでnegative loop(閉路の重みの和が負になる)を探す問題を解きたいです。

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 599

前提・実現したいこと

このページの問題を解きたいです。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

問題の概要は、入力として重み付き有向グラフ(重みは負の値も取り得る)が与えられ、そのグラフ中に閉路を構成するedgeの重みの総和が負になるような閉路があれば、possibleを出力、そうでなければnot possibleを出力させるというものです。また、グラフ探索のスタートは必ずnode0で、edge数が0のnodeは存在しないという条件があります。

//Sample Input 
2             //case数
3 3           //case1 第1引数:node数 第2引数:edge数
0 1 1000      //node0からnode1への重みは1000
1 2 15        //node1からnode2への重みは15
2 1 -42       //node2からnode1への重みは-42
4 4           //case2
0 1 10 
1 2 20 
2 3 30 
3 0 -60 

//Sample Output 
possible       // case1 
not possible       // case2

発生している問題・エラーメッセージ

おおまかな方針としては、Bellman Fold法を使いました。(https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%9E%E3%83%B3%E2%80%93%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E6%B3%95)

上記URLのdistanceの初期化については、intに無限大がないみたいなのでInteger.MAX_VALUEを使いました。

下記コードのint[][] edgesは、入力における「node○からnode△への重みは×」部分の○と△と×を、それぞれedges[i][0]、edges[i][1]、edges[i][2]に格納しておくためのものです。また、int[] distは、node○への最短経路を入れておくためのものです。

いつも通り、サンプルの入力やuDebugの入力だと正しい結果となるのですが、UVaに投げるとRuntime Errorになってしまうやつになってしまいました…… 原因が分かる方お願いします。

<追記>
ちなみにjavaではないですが、正解のコード例が載っているサイトがありました。"僕の目には"やってることは殆ど変わらないように見えますが…… https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/

該当のソースコード(修正後)

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

class Wormhole {
    public static int min (int a, int b) {
        if(a<b) return a;
        else return b;
    }

    public static void main (String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] edges;
        int[] dist;
        int tmp;

        try {
            String line;
            StringTokenizer token;
            line = br.readLine();
            int testcase = Integer.parseInt(line);

            for(int a=0; a<testcase; a++) {
                line = br.readLine();
                token = new StringTokenizer(line, " ");
                int node = Integer.parseInt(token.nextToken());  //node数
                int edge = Integer.parseInt(token.nextToken());  //edge数

               if(edge==0) {                 //ここから4行が追加部分
                 System.out.println("not possible");
                  continue;
               }

                edges = new int[edge][3];
                dist = new int[node];    //distの長さをedge数からnode数に修正

                for(int i=0; i<edge; i++) {
                    line = br.readLine();
                    token = new StringTokenizer(line, " ");
                    dist[i] = Integer.MAX_VALUE;
                    edges[i][0] = Integer.parseInt(token.nextToken());  //edges[i][0]から
                    edges[i][1] = Integer.parseInt(token.nextToken());  //edges[i][1]までの
                    edges[i][2] = Integer.parseInt(token.nextToken());  //重みはedges[i][2]
                }

                dist[0] = 0;

// Integer.MAX_VALUEにedgeの重みが足されてしまうと、値が負になり最短路判定を食らってしまうので場合分けしました

                if(node>edge) System.out.println("not possible");
                else {
                    for(int i=0; i<node-1; i++) {
                        for(int j=0; j<edge; j++) {
                            if(dist[edges[j][0]]!=Integer.MAX_VALUE)
                                dist[edges[j][1]] = 
                       min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]);
                        }
                    }         // ここまでで最短路の計算は完了

//もう1周だけ最短路の計算を繰り返したとき、最短路が変わる(=小さくなる)場所が1か所でもあれば、negative loopを持つ

                    boolean judge = false;

                    for(int i=0; i<edge; i++) {
                        tmp = dist[edges[i][1]];
                        dist[edges[i][1]] = min(dist[edges[i][1]], dist[edges[i][0]]+edges[i][2]);

                        if(tmp!=dist[edges[i][1]]) {  // distanceの値が計算前と変わっている
                            judge = true;
                            break;
                        }
                    }

                    if(judge) System.out.println("possible");
                    else System.out.println("not possible");
                }
            }

        } catch(IOException e) {
                System.out.println("IOException" + e);
                System.exit(1);
        }
    }
}

追記

edge数が0だった場合、not possibleとして次のループに移行というコードを追加して、distの長さをedge数ではなくnode数に修正したところ、KSwordOfHasteさんの仰っている入力例だとnot possibleのままなのにAcceptedされてしまいました。

このサイト(https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/)のコードはc++で書かれているみたいですが、MAX_INTに値が足されたときに負になってしまうことについて対処されてない??ように見えるのに、提出してみたところAcceptedになるし、KSwordOfHasteさんの入力例もpossibleとなります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2017/05/31 09:42

    catch内のSystem.exit(1)を削除して提出してみていただけませんか?

    キャンセル

  • RinT_hinabita39

    2017/05/31 10:41

    同じくRuntime Errorでしたね…

    キャンセル

回答 2

checkベストアンサー

+2

気づいた点だけコメントします。

  • distの要素数
    問題文の条件から、辺(ワームホール)の数は0以上、2000以下です。ベルマン–フォード法は頂点ごとの最短距離を用いる方法ですが、コードでは最短距離の配列distを頂点の数ではなく辺の数分しか用意していません。ゆえに辺の数が0の場合、dist[0]を初期化する箇所でArrayIndexOutOfBoundsExceptionが発生します。
    アドバイス:
    依存関係(距離distの要素数は頂点の数に依存するなど)をよく確認しましょう。
    境界条件(辺の数は0の場合もある)に着目しましょう。

  • 頂点数>辺数の場合not posibleとは限らないのでは?
    1
    3 2
    0 1 1
    1 0 -2
    はpossibleであるべきだと思うのですが・・・


  • ところでUVaってRuntimExceptionとしか表示されないのでしょうか?

  • 前の質問でswordoneさんがStringTokenizerがdeprecatedであることから別の方法を薦めておられます。UVaであれば入力不正はないように思えるのでScannerでも充分だと思いますが・・・

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/31 10:06

    以前の質問でScannerは遅いからBufferedReader使えと言われたそうですよ。

    キャンセル

  • 2017/05/31 10:48

    そうですね、swordoneさんの言う通りTime Limit Exceededを避けるためにScannerは使わないようにしています。また、以前にsplitを教えてもらったのですが、Stringとして扱われるために、数を分割したいときは配列を2つ用意して、1つずつint他に変換しないといけないので、メモリを無駄に食うし手間もそんなに変わらなさそうということで、結局StringTokenizer使ってます…(Stringを分割したいときはsplit使います)

    キャンセル

  • 2017/05/31 10:53

    Between any pair of star systems, there is "at most" one wormhole in either direction. とあるので、edge数が0のnodeも存在しえますね、at mostを見落としていました… 少し考えてきます。

    キャンセル

  • 2017/05/31 10:55

    UVaの判定については、Accepted、Wrong Answer、Time Limit Exceeded、Runtime Error、Compilation errorがあります。

    キャンセル

  • 2017/05/31 11:47

    >Scannerの件
    そうだったのですか。失礼しました。遅いという意識がなかったので自分も気を付けます。
    > Runtime Errorしか出してくれない
    机上で論理の正しさを検証する力が要求されるんですね。なるほど~。これは訓練になりますね!

    キャンセル

0

  • クラス名class Wormhole public class Mainでないといけないようです。
    参考:Can't reproduce a runtime error that UVa Online Judge gives me

  • dist[i] = Integer.MAX_VALUE;は、iの範囲を考えると明らかにまずいです。

  • distの最大値は問題から求まるのでInteger.MAX_VALUEを使わなくてもよいです。
    最大値で初期化すると、if(dist[edges[j][0]]!=Integer.MAX_VALUE)の判定は不要になります。
    提示されたC++コードでは、たぶんif文中で暗黙の型変換が起きているので問題なく動作しています。

Rumtime Errorになった場合は、コードを削って実行し、Error箇所を絞るようにします。
すなわちWrong answer=少なくとも実行はできる 状態までもっていくようにします。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • Java

    15772questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。