質問編集履歴
4
コードの一部修正し忘れ
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -63,13 +63,13 @@
|
|
|
63
63
|
int node = Integer.parseInt(token.nextToken()); //node数
|
|
64
64
|
int edge = Integer.parseInt(token.nextToken()); //edge数
|
|
65
65
|
|
|
66
|
-
|
|
66
|
+
if(edge==0) { //ここから4行が追加部分
|
|
67
|
-
|
|
67
|
+
System.out.println("not possible");
|
|
68
|
-
|
|
68
|
+
continue;
|
|
69
|
-
|
|
69
|
+
}
|
|
70
70
|
|
|
71
71
|
edges = new int[edge][3];
|
|
72
|
-
dist = new int[
|
|
72
|
+
dist = new int[node]; //distの長さをedge数からnode数に修正
|
|
73
73
|
|
|
74
74
|
for(int i=0; i<edge; i++) {
|
|
75
75
|
line = br.readLine();
|
|
@@ -123,5 +123,6 @@
|
|
|
123
123
|
```
|
|
124
124
|
|
|
125
125
|
###追記
|
|
126
|
-
edge数が0だった場合、not possibleとして次のループに移行というコードを追加したところ、KSwordOfHaste
|
|
127
|
-
|
|
126
|
+
edge数が0だった場合、not possibleとして次のループに移行というコードを追加して、distの長さをedge数ではなくnode数に修正したところ、KSwordOfHasteさんの仰っている入力例だとnot possibleのままなのにAcceptedされてしまいました。
|
|
127
|
+
|
|
128
|
+
このサイト(https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/)のコードはc++で書かれているみたいですが、MAX_INTに値が足されたときに負になってしまうことについて対処されてない？？ように見えるのに、提出してみたところAcceptedになるし、KSwordOfHasteさんの入力例もpossibleとなります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう？
|
3
コードを修正したところ、新たな疑問点が出たので
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -34,7 +34,7 @@
|
|
|
34
34
|
＜追記＞
|
|
35
35
|
ちなみにjavaではないですが、正解のコード例が載っているサイトがありました。"僕の目には"やってることは殆ど変わらないように見えますが…… https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/
|
|
36
36
|
|
|
37
|
-
###該当のソースコード
|
|
37
|
+
###該当のソースコード（修正後）
|
|
38
38
|
```java
|
|
39
39
|
import java.util.*;
|
|
40
40
|
import java.io.*;
|
|
@@ -63,6 +63,11 @@
|
|
|
63
63
|
int node = Integer.parseInt(token.nextToken()); //node数
|
|
64
64
|
int edge = Integer.parseInt(token.nextToken()); //edge数
|
|
65
65
|
|
|
66
|
+
if(edge==0) { //ここから4行が追加部分
|
|
67
|
+
System.out.println("not possible");
|
|
68
|
+
continue;
|
|
69
|
+
}
|
|
70
|
+
|
|
66
71
|
edges = new int[edge][3];
|
|
67
72
|
dist = new int[edge];
|
|
68
73
|
|
|
@@ -117,5 +122,6 @@
|
|
|
117
122
|
|
|
118
123
|
```
|
|
119
124
|
|
|
120
|
-
###
|
|
121
|
-
|
|
125
|
+
###追記
|
|
126
|
+
edge数が0だった場合、not possibleとして次のループに移行というコードを追加したところ、KSwordOfHaste
|
|
127
|
+
さんの仰っている入力例だとnot possibleのままなのにAcceptedされてしまいました。このサイト(https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/)のコードはc++で書かれているみたいですが、MAX_INTに値が足されたときに負になってしまうことについて対処されてない？？ように見えるのに、提出してみたところAcceptedになるし、KSwordOfHasteさんの入力例もpossibleとなります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう？
|
2
コードの解説を付け足しました
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -76,15 +76,18 @@
|
|
|
76
76
|
}
|
|
77
77
|
|
|
78
78
|
dist[0] = 0;
|
|
79
|
+
|
|
79
|
-
|
|
80
|
+
// Integer.MAX_VALUEにedgeの重みが足されてしまうと、値が負になり最短路判定を食らってしまうので場合分けしました
|
|
81
|
+
|
|
80
82
|
if(node>edge) System.out.println("not possible");
|
|
81
83
|
else {
|
|
82
84
|
for(int i=0; i<node-1; i++) {
|
|
83
85
|
for(int j=0; j<edge; j++) {
|
|
84
86
|
if(dist[edges[j][0]]!=Integer.MAX_VALUE)
|
|
87
|
+
dist[edges[j][1]] =
|
|
85
|
-
|
|
88
|
+
min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]);
|
|
86
89
|
}
|
|
87
|
-
}
|
|
90
|
+
} // ここまでで最短路の計算は完了
|
|
88
91
|
|
|
89
92
|
//もう1周だけ最短路の計算を繰り返したとき、最短路が変わる(=小さくなる)場所が1か所でもあれば、negative loopを持つ
|
|
90
93
|
|
1
参考になりそうなURLを足しました
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -31,6 +31,9 @@
|
|
|
31
31
|
|
|
32
32
|
いつも通り、サンプルの入力やuDebugの入力だと正しい結果となるのですが、UVaに投げるとRuntime Errorになってしまうやつになってしまいました…… 原因が分かる方お願いします。
|
|
33
33
|
|
|
34
|
+
＜追記＞
|
|
35
|
+
ちなみにjavaではないですが、正解のコード例が載っているサイトがありました。"僕の目には"やってることは殆ど変わらないように見えますが…… https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/
|
|
36
|
+
|
|
34
37
|
###該当のソースコード
|
|
35
38
|
```java
|
|
36
39
|
import java.util.*;
|