[ BOJ 백준 10360번 - The Mountain of Gold? ] 해설 및 코드

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

 

목적

Ledang Pool들을 거쳐 Ledang Mountain에 과거에 도달할 수 있는지 구하자.

 

접근법

1. 음의 사이클에서 0지점(Ledang Mountain)으로 가는 길이 있는지 확인하면 된다.

2. 음의 사이클 판별을 위해 벨만 포드 알고리즘을 적용하고, 그때마다 현재 지점에서 0지점으로 갈 수 있는 지 여부를 배열에 저장한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
const int INF = 2e9;
int n, m, e[2000][3], s[1000];
bool t[1000];
 
bool sol() {
    bool first = true;
    cin >> n >> m;
 
    f(i, 1, n)s[i] = INF, t[i] = false;
    s[0] = 0;
    t[0] = true;
    f(i, 0, m) {
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        if (t[e[i][1]])t[e[i][0]] = true;
    }
 
    f(k, 1, n)f(i, 0, m)if (s[e[i][0]] != INF) {
        int tmp = s[e[i][0]] + e[i][2];
        if (s[e[i][1]] > tmp)s[e[i][1]] = tmp;
        if (t[e[i][1]])t[e[i][0]] = true;
    }
    f(i, 0, m)if (s[e[i][0]] != INF
        && s[e[i][1]] > s[e[i][0]] + e[i][2]
        && t[e[i][1]])return true;
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    f(i, 0, t) {
        cout << "Case #" << i + 1 << ": ";;
        if (!sol())cout << "not ";
        cout << "possible\n";
    }
    return 0;
}

 

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

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