[ BOJ 백준 1219번 - 오민식의 고민 ] 해설 및 코드

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

목적

출발 도시에서 도착 도시까지 가는데, 중간에 여러 도시를 거쳐 얻을 수 있는 최대 이윤을 구하자.

 

접근법

1. 사이클이 발생 여부를 확인하기 위해 벨만 포드 알고리즘을 적용한다. 

2. 사이클이 발생할 경우 사이클에서 도착 도시까지 가는 경로가 존재하는지 확인하기 위해 플로이드 와샬 알고리즘을 적용한다.

3. 발생할 수 있는 최대 이윤은 int 범위를 넘어갈 수 있으므로 타입에 주의한다. (100개의 도시가 100개의 교통수단으로 가장 큰 사이클을 형성할 때, 벨만 포드 알고리즘 적용 시, 비용이 100*100*1000000 = 10^10 까지 커질 수 있기 때문이다.)

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
typedef long long ll;
 
const int INF = -1e8;
int n, src, dst, m, money[100], e[100][3];
ll s[100], t[100];
bool p[100][100]{};
 
void one_cycle(ll s[]) {
    f(i, 0, m) if (s[e[i][0]] != INF) {
        ll tmp = s[e[i][0]] - e[i][2] + money[e[i][1]];
        if (s[e[i][1]] < tmp)s[e[i][1]] = tmp;
    }
}
 
void sol() {
    s[src] = money[src];
    f(k, 1, n)one_cycle(s);
    f(i, 0, n)t[i] = s[i];
    one_cycle(t);
    f(i, 0, n)if (t[i] != s[i]&&p[i][dst]) {
        cout << "Gee";
        return;
    }
    cout << s[dst];
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> src >> dst >> m;
    f(i, 0, m) {
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        p[e[i][0]][e[i][1]] = true;
    }
    f(i, 0, n)cin >> money[i], s[i] = INF;
    f(k, 0, n)f(i, 0, n)f(j, 0, n)if (p[i][k] && p[k][j])p[i][j] = true;
    
    if (src!=dst&&!p[src][dst]) cout << "gg";
    else sol();
    
    return 0;
}

 

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

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