###前提・実現したいこと
このページの問題を解きたいです。
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されてしまいました。
回答2件
あなたの回答
tips
プレビュー