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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Java

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

Q&A

解決済

2回答

2138閲覧

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

RinT_hinabita39

総合スコア28

Java

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

0グッド

1クリップ

投稿2017/05/30 16:06

編集2017/05/31 03:56

###前提・実現したいこと
このページの問題を解きたいです。
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/

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

java

1import java.util.*; 2import java.io.*; 3 4class Wormhole { 5 public static int min (int a, int b) { 6 if(a<b) return a; 7 else return b; 8 } 9 10 public static void main (String[] args) { 11 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 12 int[][] edges; 13 int[] dist; 14 int tmp; 15 16 try { 17 String line; 18 StringTokenizer token; 19 line = br.readLine(); 20 int testcase = Integer.parseInt(line); 21 22 for(int a=0; a<testcase; a++) { 23 line = br.readLine(); 24 token = new StringTokenizer(line, " "); 25 int node = Integer.parseInt(token.nextToken()); //node数 26 int edge = Integer.parseInt(token.nextToken()); //edge数 27 28 if(edge==0) { //ここから4行が追加部分 29 System.out.println("not possible"); 30 continue; 31 } 32 33 edges = new int[edge][3]; 34 dist = new int[node]; //distの長さをedge数からnode数に修正 35 36 for(int i=0; i<edge; i++) { 37 line = br.readLine(); 38 token = new StringTokenizer(line, " "); 39 dist[i] = Integer.MAX_VALUE; 40 edges[i][0] = Integer.parseInt(token.nextToken()); //edges[i][0]から 41 edges[i][1] = Integer.parseInt(token.nextToken()); //edges[i][1]までの 42 edges[i][2] = Integer.parseInt(token.nextToken()); //重みはedges[i][2] 43 } 44 45 dist[0] = 0; 46 47// Integer.MAX_VALUEにedgeの重みが足されてしまうと、値が負になり最短路判定を食らってしまうので場合分けしました 48 49 if(node>edge) System.out.println("not possible"); 50 else { 51 for(int i=0; i<node-1; i++) { 52 for(int j=0; j<edge; j++) { 53 if(dist[edges[j][0]]!=Integer.MAX_VALUE) 54 dist[edges[j][1]] = 55 min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]); 56 } 57 } // ここまでで最短路の計算は完了 58 59//もう1周だけ最短路の計算を繰り返したとき、最短路が変わる(=小さくなる)場所が1か所でもあれば、negative loopを持つ 60 61 boolean judge = false; 62 63 for(int i=0; i<edge; i++) { 64 tmp = dist[edges[i][1]]; 65 dist[edges[i][1]] = min(dist[edges[i][1]], dist[edges[i][0]]+edges[i][2]); 66 67 if(tmp!=dist[edges[i][1]]) { // distanceの値が計算前と変わっている 68 judge = true; 69 break; 70 } 71 } 72 73 if(judge) System.out.println("possible"); 74 else System.out.println("not possible"); 75 } 76 } 77 78 } catch(IOException e) { 79 System.out.println("IOException" + e); 80 System.exit(1); 81 } 82 } 83} 84

###追記
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となります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう?

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2017/05/31 00:42

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

回答2

0

ベストアンサー

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

  • 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 00:47

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2017/05/31 01:06

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

2017/05/31 01:48

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

2017/05/31 01:53

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

2017/05/31 01:55

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

2017/05/31 02:47

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

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=少なくとも実行はできる 状態までもっていくようにします。

投稿2017/06/01 02:52

can110

総合スコア38233

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問