728x90
반응형
1956번: 운동
문제
https://www.acmicpc.net/problem/1956
풀이
어느 점에서 다른 한 점까지 갔다가 다시 출발점으로 돌아오는 사이클의 길이의 최솟값을 찾는 문제다. 플로이드 워셜 알고리즘으로 각 정점 간 거리를 구하고 모든 경우의 수를 탐색하며 최솟값을 찾는 방식으로 풀었다.
코드
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int V, E, dist[401][401];
cin >> V >> E;
// dist 배열 초기화
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
dist[i][j] = i == j ? 0 : INF;
// 간선 입력
while (E--) {
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = c;
}
// 플로이드 워셜
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
// i->j + j->i 더한 값의 최솟값 비교
int ans = INF;
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
if (dist[i][j]) // 거리가 0이 아니면!
ans = min(ans, dist[i][j] + dist[j][i]);
// 사이클이 없으면 -1 출력
cout << (ans != INF ? ans : -1) << '\n';
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 2458 키 순서 (0) | 2023.02.26 |
---|---|
[백준 / BOJ] C++ 13168 내일로 여행 (0) | 2023.02.25 |
[백준 / BOJ] C++ 1613 역사 (0) | 2023.02.25 |
[백준 / BOJ] C++ 1389 케빈 베이컨의 6단계 법칙 (0) | 2023.02.25 |
[백준 / BOJ] C++ 11403 경로 찾기 (0) | 2023.02.25 |