[ BOJ 백준 1956번 - 운동 ] 해설 및 코드

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

목적

도로의 길이의 합이 가장 작은 사이클을 찾자.

 

접근법

1. a마을에서 출발하여 a마을로 도착하는 길이의 최소값을 구해야 한다. 

2. 다대다 경로 검색 알고리즘인 플로이드 와샬을 적용하여, s[i][i] (i는1이상 v이하)의 최소값을 찾는다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define N 401
using namespace std;
 
const int INF = N * 1e4;
int s[N][N];
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int v, e; cin >> v >> e;
    f(i, 1, v)f(j, 1, v) s[i][j] = INF;
 
    while (e--) {
        int a, b, c; cin >> a >> b >> c;
        s[a][b] = c;
    }
 
    f(k, 1, v)f(i, 1, v)f(j, 1, v){
        int tmp = s[i][k] + s[k][j];
        if (s[i][j] > tmp)s[i][j] = tmp;
    }
 
    int ans = INF;
    f(i, 1, v)if (ans > s[i][i])ans = s[i][i];
    
    cout << (ans == INF ? -1 : ans);
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.