1956번: 운동

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

문제 풀이

도로 길이의 합이 최소가 되는 사이클을 찾아야 하므로, 모든 정점간의 최단거리가 필요하다.
따라서 플로이드 알고리즘을 통해 정점간 최단거리를 먼저 구한 후, 모든 정점 쌍에 대하여 (v1, v2) d(v1, v2) + d(v2, v1) 값의 최솟값을 구한다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int v, e, adj[400][400];

int floyd() {
    int ret = 987654321;
    for(int i = 0; i < v; i++) adj[i][i] = 0;
    for(int k = 0; k < v; k++)
        for(int i = 0; i < v; i++)
            for(int j = 0; j < v; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    for(int i = 0; i < v; i++)
        for(int j = 0; j < v; j++)
            if(i != j)
                ret = min(ret, adj[i][j] + adj[j][i]);
    return ret;
}

int main() {
    scanf("%d %d", &v, &e);
    for(int i = 0; i < v; i++)
        for(int j = 0; j < v; j++)
                adj[i][j] = 987654321;
    for(int i = 0; i < e; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        adj[a][b] = min(adj[a][b], c);
    }
    int ret = floyd();
    if(ret == 987654321) printf("-1");
    else printf("%d", ret);
    return 0;
}

배운 점

처음에 너무 복잡하게 생각하여 문제를 해결하는데 시간이 꽤 걸렸다. V값의 범위가 최대 400이므로 플로이드 알고리즘( O(V^3) )을 수행해도 문제 없고, 모든 정점 쌍에 대해 사이클의 길이를( O(V^2) ) 구해도 문제 없었다. 변수의 범위와 시간복잡도를 잘 파악하여 문제를 접근하는 습관을 들이도록 하자.