백준 1956번 (운동, C++, Floyd-Warshall) / 추가 반례 [BAEKJOON]

운동

https://www.acmicpc.net/problem/1956

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초192 MB170446747496540.310%

문제

V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다.

도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다.

마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.

당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다.

운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다.

단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.

도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오.

두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

입력

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1))

다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다.

a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의)

거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다.

운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3 4
1 2 1
3 2 1
1 3 5
2 3 2

예제 출력 1

3

출처

알고리즘 분류


접근 방법

통과된 코드

#include <iostream>
#include <vector>

using namespace std;

constexpr int INF = INT32_MAX / 2; 

constexpr int MAX = 401;

vector<pair<int, int>> graph[MAX];

int disArr[MAX][MAX];

// V 개의 마을, E 개의 도로
int V, E, a, b, c;

int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> V >> E;

    // 도로의 정보를 입력
    for (int i = 0; i < E; i++) {

        cin >> a >> b >> c;
        // 일방통행
        graph[a].push_back(make_pair(b, c));

    }

    // 최단 거리 배열 disArr 배열을 INF 초기화
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++) {

            if (i == j) disArr[i][j] = 0;
            else disArr[i][j] = INF;

        }
    }

    // 경로 가중치 입력
    for (int i = 1; i <= V; i++) { // 시작 정점
        for (int j = 0; j < graph[i].size(); j++) {

            int v = graph[i][j].first; // 도착점
            int weight = graph[i][j].second; // 가중치

            if (disArr[i][v] > weight) disArr[i][v] = weight;
        }
    }

    // 플로이드 워셜
    for (int k = 1; k <= V; k++) {
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i == j) continue;
                else disArr[i][j] = min(disArr[i][j], disArr[i][k] + disArr[k][j]);
            }
        }
    }
    
    int result = INF;
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++) {
            // 출발 지점과 도착 지점이 같거나 둘중 하나라도 가중치가 무한대라면 넘어간다. 
            if (i == j || disArr[i][j] == INF || disArr[j][i] == INF) continue;
            // 최소 가중치를 찾는다.
            result = min(result, disArr[i][j] + disArr[j][i]);            
        }
    }

    if (result == INF) cout << "-1";
    else cout << result;

    return 0;
}

추가 반례

https://www.acmicpc.net/board/search/all/problem/1956

예제 입력 A

5 8
2 5 5
1 3 5
1 5 9
2 4 2
4 1 9
3 2 10
3 4 9
4 3 7

예제 출력 A

16

예제 입력 B

4 3
2 3 1
3 4 1
4 2 1

예제 출력 B

3

예제 입력 C

3 6
1 2 100
1 2 1
3 2 3
3 2 70
1 3 4
2 3 5

예제 출력 C

8

예제 입력 D

400 400
1 2 10000
2 3 10000
3 4 10000
4 5 10000
5 6 10000
6 7 10000
7 8 10000
8 9 10000
9 10 10000
10 11 10000
11 12 10000
12 13 10000
13 14 10000
14 15 10000
15 16 10000
16 17 10000
17 18 10000
18 19 10000
19 20 10000
20 21 10000
21 22 10000
22 23 10000
23 24 10000
24 25 10000
25 26 10000
26 27 10000
27 28 10000
28 29 10000
29 30 10000
30 31 10000
31 32 10000
32 33 10000
33 34 10000
34 35 10000
35 36 10000
36 37 10000
37 38 10000
38 39 10000
39 40 10000
40 41 10000
41 42 10000
42 43 10000
43 44 10000
44 45 10000
45 46 10000
46 47 10000
47 48 10000
48 49 10000
49 50 10000
50 51 10000
51 52 10000
52 53 10000
53 54 10000
54 55 10000
55 56 10000
56 57 10000
57 58 10000
58 59 10000
59 60 10000
60 61 10000
61 62 10000
62 63 10000
63 64 10000
64 65 10000
65 66 10000
66 67 10000
67 68 10000
68 69 10000
69 70 10000
70 71 10000
71 72 10000
72 73 10000
73 74 10000
74 75 10000
75 76 10000
76 77 10000
77 78 10000
78 79 10000
79 80 10000
80 81 10000
81 82 10000
82 83 10000
83 84 10000
84 85 10000
85 86 10000
86 87 10000
87 88 10000
88 89 10000
89 90 10000
90 91 10000
91 92 10000
92 93 10000
93 94 10000
94 95 10000
95 96 10000
96 97 10000
97 98 10000
98 99 10000
99 100 10000
100 101 10000
101 102 10000
102 103 10000
103 104 10000
104 105 10000
105 106 10000
106 107 10000
107 108 10000
108 109 10000
109 110 10000
110 111 10000
111 112 10000
112 113 10000
113 114 10000
114 115 10000
115 116 10000
116 117 10000
117 118 10000
118 119 10000
119 120 10000
120 121 10000
121 122 10000
122 123 10000
123 124 10000
124 125 10000
125 126 10000
126 127 10000
127 128 10000
128 129 10000
129 130 10000
130 131 10000
131 132 10000
132 133 10000
133 134 10000
134 135 10000
135 136 10000
136 137 10000
137 138 10000
138 139 10000
139 140 10000
140 141 10000
141 142 10000
142 143 10000
143 144 10000
144 145 10000
145 146 10000
146 147 10000
147 148 10000
148 149 10000
149 150 10000
150 151 10000
151 152 10000
152 153 10000
153 154 10000
154 155 10000
155 156 10000
156 157 10000
157 158 10000
158 159 10000
159 160 10000
160 161 10000
161 162 10000
162 163 10000
163 164 10000
164 165 10000
165 166 10000
166 167 10000
167 168 10000
168 169 10000
169 170 10000
170 171 10000
171 172 10000
172 173 10000
173 174 10000
174 175 10000
175 176 10000
176 177 10000
177 178 10000
178 179 10000
179 180 10000
180 181 10000
181 182 10000
182 183 10000
183 184 10000
184 185 10000
185 186 10000
186 187 10000
187 188 10000
188 189 10000
189 190 10000
190 191 10000
191 192 10000
192 193 10000
193 194 10000
194 195 10000
195 196 10000
196 197 10000
197 198 10000
198 199 10000
199 200 10000
200 201 10000
201 202 10000
202 203 10000
203 204 10000
204 205 10000
205 206 10000
206 207 10000
207 208 10000
208 209 10000
209 210 10000
210 211 10000
211 212 10000
212 213 10000
213 214 10000
214 215 10000
215 216 10000
216 217 10000
217 218 10000
218 219 10000
219 220 10000
220 221 10000
221 222 10000
222 223 10000
223 224 10000
224 225 10000
225 226 10000
226 227 10000
227 228 10000
228 229 10000
229 230 10000
230 231 10000
231 232 10000
232 233 10000
233 234 10000
234 235 10000
235 236 10000
236 237 10000
237 238 10000
238 239 10000
239 240 10000
240 241 10000
241 242 10000
242 243 10000
243 244 10000
244 245 10000
245 246 10000
246 247 10000
247 248 10000
248 249 10000
249 250 10000
250 251 10000
251 252 10000
252 253 10000
253 254 10000
254 255 10000
255 256 10000
256 257 10000
257 258 10000
258 259 10000
259 260 10000
260 261 10000
261 262 10000
262 263 10000
263 264 10000
264 265 10000
265 266 10000
266 267 10000
267 268 10000
268 269 10000
269 270 10000
270 271 10000
271 272 10000
272 273 10000
273 274 10000
274 275 10000
275 276 10000
276 277 10000
277 278 10000
278 279 10000
279 280 10000
280 281 10000
281 282 10000
282 283 10000
283 284 10000
284 285 10000
285 286 10000
286 287 10000
287 288 10000
288 289 10000
289 290 10000
290 291 10000
291 292 10000
292 293 10000
293 294 10000
294 295 10000
295 296 10000
296 297 10000
297 298 10000
298 299 10000
299 300 10000
300 301 10000
301 302 10000
302 303 10000
303 304 10000
304 305 10000
305 306 10000
306 307 10000
307 308 10000
308 309 10000
309 310 10000
310 311 10000
311 312 10000
312 313 10000
313 314 10000
314 315 10000
315 316 10000
316 317 10000
317 318 10000
318 319 10000
319 320 10000
320 321 10000
321 322 10000
322 323 10000
323 324 10000
324 325 10000
325 326 10000
326 327 10000
327 328 10000
328 329 10000
329 330 10000
330 331 10000
331 332 10000
332 333 10000
333 334 10000
334 335 10000
335 336 10000
336 337 10000
337 338 10000
338 339 10000
339 340 10000
340 341 10000
341 342 10000
342 343 10000
343 344 10000
344 345 10000
345 346 10000
346 347 10000
347 348 10000
348 349 10000
349 350 10000
350 351 10000
351 352 10000
352 353 10000
353 354 10000
354 355 10000
355 356 10000
356 357 10000
357 358 10000
358 359 10000
359 360 10000
360 361 10000
361 362 10000
362 363 10000
363 364 10000
364 365 10000
365 366 10000
366 367 10000
367 368 10000
368 369 10000
369 370 10000
370 371 10000
371 372 10000
372 373 10000
373 374 10000
374 375 10000
375 376 10000
376 377 10000
377 378 10000
378 379 10000
379 380 10000
380 381 10000
381 382 10000
382 383 10000
383 384 10000
384 385 10000
385 386 10000
386 387 10000
387 388 10000
388 389 10000
389 390 10000
390 391 10000
391 392 10000
392 393 10000
393 394 10000
394 395 10000
395 396 10000
396 397 10000
397 398 10000
398 399 10000
399 400 10000
400 1 10000

예제 출력 D

4000000

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top