운동
https://www.acmicpc.net/problem/1956
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 192 MB | 17044 | 6747 | 4965 | 40.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
![백준 11651번 (좌표 정렬하기 2, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/2022/10/boj-og-1-2048x1070-1-1024x535.png)
![백준 1219번 (오민식의 고민, C++, Bellman–Ford) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og-1.png)