https://www.acmicpc.net/problem/1956
경로가 주어지고 v ~-> v로 돌아올 수 있는 최소 경로를 구하는 문제입니다.
V가 400으로 플로이드 와샬 방법으로 모든 경로간 최소 경로를 구하고 그중 가장 작은 v ~-> v 비용을 출력하면 됩니다.
플로이드 와샬의 아이디어는 어떤 정점 i를 거쳐가는 모든 경로 v ~-> i -~> u를 완전탐색 O(n^3)로 구할 수 있습니다.
초기값을 입력 경로로 넣어주고 나머지는 꽤 큰값 (1e9)로 초기화한 뒤 3중 포문으로 구해 나가는 코드입니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <math.h>
#include <memory.h>
#include <set>
using namespace std;
int n, m;
int buf[401][401];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
buf[i][j] = 1e9;
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
buf[a][b] = min(buf[a][b], c);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
buf[j][k] = min(buf[j][k], buf[j][i] + buf[i][k]);
}
}
}
int ans = 2e9;
for (int i = 1; i <= n; i++) {
ans = min(ans, buf[i][i]);
}
cout << (ans == 1e9 ? -1 :ans);
}
반응형
'알고리즘' 카테고리의 다른 글
[BOJ] 백준 1002번: 터렛 (1) | 2020.08.11 |
---|---|
유니온 파인드 (Union Find) 혹은 분리 집합 (Disjoint Set) (0) | 2020.08.09 |
[BOJ] 백준 9370번: 미확인 도착지 (0) | 2020.08.09 |
최대 공약수와 최소 공배수 알고리즘 (0) | 2020.08.09 |
[BOJ] 백준 10217번: KCM Travel (0) | 2020.08.09 |