teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問有向グラフでnegative loop(閉路の重みの和が負になる)を探す問題を解きたいです。

編集履歴

質問編集履歴

4

コードの一部修正し忘れ

2017/05/31 03:56

投稿

RinT_hinabita39
RinT_hinabita39

スコア28

test CHANGED
File without changes
test CHANGED
@@ -128,102 +128,102 @@
128
128
 
129
129
 
130
130
 
131
- if(edge==0) { //ここから4行が追加部分
131
+ if(edge==0) { //ここから4行が追加部分
132
-
132
+
133
- System.out.println("not possible");
133
+ System.out.println("not possible");
134
-
134
+
135
- continue;
135
+ continue;
136
+
137
+ }
138
+
139
+
140
+
141
+ edges = new int[edge][3];
142
+
143
+ dist = new int[node]; //distの長さをedge数からnode数に修正
144
+
145
+
146
+
147
+ for(int i=0; i<edge; i++) {
148
+
149
+ line = br.readLine();
150
+
151
+ token = new StringTokenizer(line, " ");
152
+
153
+ dist[i] = Integer.MAX_VALUE;
154
+
155
+ edges[i][0] = Integer.parseInt(token.nextToken()); //edges[i][0]から
156
+
157
+ edges[i][1] = Integer.parseInt(token.nextToken()); //edges[i][1]までの
158
+
159
+ edges[i][2] = Integer.parseInt(token.nextToken()); //重みはedges[i][2]
136
160
 
137
161
  }
138
162
 
163
+
164
+
139
-
165
+ dist[0] = 0;
166
+
167
+
168
+
140
-
169
+ // Integer.MAX_VALUEにedgeの重みが足されてしまうと、値が負になり最短路判定を食らってしまうので場合分けしました
170
+
171
+
172
+
173
+ if(node>edge) System.out.println("not possible");
174
+
175
+ else {
176
+
177
+ for(int i=0; i<node-1; i++) {
178
+
141
- edges = new int[edge][3];
179
+ for(int j=0; j<edge; j++) {
180
+
142
-
181
+ if(dist[edges[j][0]]!=Integer.MAX_VALUE)
182
+
143
- dist = new int[edge];
183
+ dist[edges[j][1]] =
184
+
144
-
185
+ min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]);
186
+
145
-
187
+ }
188
+
146
-
189
+ } // ここまでで最短路の計算は完了
190
+
191
+
192
+
193
+ //もう1周だけ最短路の計算を繰り返したとき、最短路が変わる(=小さくなる)場所が1か所でもあれば、negative loopを持つ
194
+
195
+
196
+
197
+ boolean judge = false;
198
+
199
+
200
+
147
- for(int i=0; i<edge; i++) {
201
+ for(int i=0; i<edge; i++) {
148
-
202
+
149
- line = br.readLine();
203
+ tmp = dist[edges[i][1]];
204
+
150
-
205
+ dist[edges[i][1]] = min(dist[edges[i][1]], dist[edges[i][0]]+edges[i][2]);
206
+
207
+
208
+
209
+ if(tmp!=dist[edges[i][1]]) { // distanceの値が計算前と変わっている
210
+
211
+ judge = true;
212
+
213
+ break;
214
+
215
+ }
216
+
217
+ }
218
+
219
+
220
+
151
- token = new StringTokenizer(line, " ");
221
+ if(judge) System.out.println("possible");
152
-
153
- dist[i] = Integer.MAX_VALUE;
222
+
154
-
155
- edges[i][0] = Integer.parseInt(token.nextToken()); //edges[i][0]から
223
+ else System.out.println("not possible");
156
-
157
- edges[i][1] = Integer.parseInt(token.nextToken()); //edges[i][1]までの
158
-
159
- edges[i][2] = Integer.parseInt(token.nextToken()); //重みはedges[i][2]
160
224
 
161
225
  }
162
226
 
163
-
164
-
165
- dist[0] = 0;
166
-
167
-
168
-
169
- // Integer.MAX_VALUEにedgeの重みが足されてしまうと、値が負になり最短路判定を食らってしまうので場合分けしました
170
-
171
-
172
-
173
- if(node>edge) System.out.println("not possible");
174
-
175
- else {
176
-
177
- for(int i=0; i<node-1; i++) {
178
-
179
- for(int j=0; j<edge; j++) {
180
-
181
- if(dist[edges[j][0]]!=Integer.MAX_VALUE)
182
-
183
- dist[edges[j][1]] =
184
-
185
- min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]);
186
-
187
- }
188
-
189
- } // ここまでで最短路の計算は完了
190
-
191
-
192
-
193
- //もう1周だけ最短路の計算を繰り返したとき、最短路が変わる(=小さくなる)場所が1か所でもあれば、negative loopを持つ
194
-
195
-
196
-
197
- boolean judge = false;
198
-
199
-
200
-
201
- for(int i=0; i<edge; i++) {
202
-
203
- tmp = dist[edges[i][1]];
204
-
205
- dist[edges[i][1]] = min(dist[edges[i][1]], dist[edges[i][0]]+edges[i][2]);
206
-
207
-
208
-
209
- if(tmp!=dist[edges[i][1]]) { // distanceの値が計算前と変わっている
210
-
211
- judge = true;
212
-
213
- break;
214
-
215
- }
216
-
217
- }
218
-
219
-
220
-
221
- if(judge) System.out.println("possible");
222
-
223
- else System.out.println("not possible");
224
-
225
- }
226
-
227
227
  }
228
228
 
229
229
 
@@ -248,6 +248,8 @@
248
248
 
249
249
  ###追記
250
250
 
251
- edge数が0だった場合、not possibleとして次のループに移行というコードを追加したところ、KSwordOfHaste
252
-
253
- さんの仰っている入力例だとnot possibleのままなのにAcceptedされてしまいました。このサイト(https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/)のコードはc++で書かれているみたいですが、MAX_INTに値が足されたときに負になってしまうことについて対処されてない？？ように見えるのに、提出してみたところAcceptedになるし、KSwordOfHasteさんの入力例もpossibleとなります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう？
251
+ edge数が0だった場合、not possibleとして次のループに移行というコードを追加して、distの長さをedge数ではなくnode数に修正したところ、KSwordOfHasteさんの仰っている入力例だとnot possibleのままなのにAcceptedされてしまいました。
252
+
253
+
254
+
255
+ このサイト(https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/)のコードはc++で書かれているみたいですが、MAX_INTに値が足されたときに負になってしまうことについて対処されてない？？ように見えるのに、提出してみたところAcceptedになるし、KSwordOfHasteさんの入力例もpossibleとなります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう？

3

コードを修正したところ、新たな疑問点が出たので

2017/05/31 03:56

投稿

RinT_hinabita39
RinT_hinabita39

スコア28

test CHANGED
File without changes
test CHANGED
@@ -70,7 +70,7 @@
70
70
 
71
71
 
72
72
 
73
- ###該当のソースコード
73
+ ###該当のソースコード（修正後）
74
74
 
75
75
  ```java
76
76
 
@@ -128,6 +128,16 @@
128
128
 
129
129
 
130
130
 
131
+ if(edge==0) { //ここから4行が追加部分
132
+
133
+ System.out.println("not possible");
134
+
135
+ continue;
136
+
137
+ }
138
+
139
+
140
+
131
141
  edges = new int[edge][3];
132
142
 
133
143
  dist = new int[edge];
@@ -236,6 +246,8 @@
236
246
 
237
247
 
238
248
 
239
- ###試したこと
240
-
241
- このコードにする前にもRuntime Errorが出て、edgeよりnodeの方が大きいときは閉路ができない(木構造になる)ことに気付き(例えばedgeが2でnodeが3のとき、そのままやるとdistanceの計算において、distanceの配列の大きさを超えたインデックスを呼ばれる可能性がある)、木になる時は直ちにnot possibleにするように直しましたが、それでもまたRuntime Errorとなってしまいました……
249
+ ###追記
250
+
251
+ edge数が0だった場合、not possibleとして次のループに移行というコードを追加したところ、KSwordOfHaste
252
+
253
+ さんの仰っている入力例だとnot possibleのままなのにAcceptedされてしまいました。このサイト(https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/)のコードはc++で書かれているみたいですが、MAX_INTに値が足されたときに負になってしまうことについて対処されてない？？ように見えるのに、提出してみたところAcceptedになるし、KSwordOfHasteさんの入力例もpossibleとなります。僕のコードと方針的には大差ないと思うのですが、何が違うのでしょう？

2

コードの解説を付け足しました

2017/05/31 03:53

投稿

RinT_hinabita39
RinT_hinabita39

スコア28

test CHANGED
File without changes
test CHANGED
@@ -154,7 +154,11 @@
154
154
 
155
155
  dist[0] = 0;
156
156
 
157
+
158
+
157
-
159
+ // Integer.MAX_VALUEにedgeの重みが足されてしまうと、値が負になり最短路判定を食らってしまうので場合分けしました
160
+
161
+
158
162
 
159
163
  if(node>edge) System.out.println("not possible");
160
164
 
@@ -166,11 +170,13 @@
166
170
 
167
171
  if(dist[edges[j][0]]!=Integer.MAX_VALUE)
168
172
 
173
+ dist[edges[j][1]] =
174
+
169
- dist[edges[j][1]] = min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]);
175
+ min(dist[edges[j][1]], dist[edges[j][0]]+edges[j][2]);
170
176
 
171
177
  }
172
178
 
173
- } // ここまでで最短路の計算は完了
179
+ } // ここまでで最短路の計算は完了
174
180
 
175
181
 
176
182
 

1

参考になりそうなURLを足しました

2017/05/30 16:16

投稿

RinT_hinabita39
RinT_hinabita39

スコア28

test CHANGED
File without changes
test CHANGED
@@ -64,6 +64,12 @@
64
64
 
65
65
 
66
66
 
67
+ ＜追記＞
68
+
69
+ ちなみにjavaではないですが、正解のコード例が載っているサイトがありました。"僕の目には"やってることは殆ど変わらないように見えますが…… https://tausiq.wordpress.com/2010/09/01/uva-558-wormholes/
70
+
71
+
72
+
67
73
  ###該当のソースコード
68
74
 
69
75
  ```java