백준 - 1956 운동

문제 링크입니다 : https://www.acmicpc.net/problem/1956

1956번: 운동

 

 

플로이드 와샬 문제이다. 사이클 구하는건 i -> j 경로랑 j -> i 경로가 있는지만 확인하면 된다.

 

 

 

#include <iostream>
#include <vector>
#define INF 987654321

using namespace std;

int V, E;

vector<vector<int>> board;

vector<vector<int>> floydWarshall() {
    vector<vector<int>> ret;

    ret = board;

    for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
            for(int j = 0; j < V; j++) {
                if(ret[i][k] + ret[k][j] < ret[i][j]) {
                    ret[i][j] = ret[i][k] + ret[k][j];
                }
            }
        }
    }
    return ret;
}


int main() {
    cin >> V >> E;
    board.assign(V, vector<int>(V, INF));

    int u, v, cost;
    for(int i = 0; i < E; i++) {
        cin >> u >> v >> cost;
        if(board[u - 1][v - 1] > cost) {
            board[u - 1][v - 1] = cost;
        }
    }

    for(int i = 0; i < V; i++) {
        board[i][i] = 0;
    }


    vector<vector<int>> temp = floydWarshall();

    int min = INF;
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            if(i == j) continue;
            if(temp[i][j] == INF || temp[j][i] == INF) continue;
            int cycle = temp[i][j] + temp[j][i];
            if(cycle < min) {
                min = cycle;
            }
        }
    }

    if(min == INF) {
        cout << -1;
    } else {
        cout << min;
    }



    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~