[백준] 오민식의 고민 c++

오민식의 고민 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

17697

3723

2309

18.727%

문제

오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.

오민식은 고민에 빠졌다.

어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.

오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 하려고 한다. 이 최댓값을 구하는 프로그램을 작성하시오.

오민식이 버는 돈보다 쓰는 돈이 많다면, 도착 도시에 도착할 때 가지고 있는 돈의 액수가 음수가 될 수도 있다. 또, 같은 도시를 여러 번 방문할 수 있으며, 그 도시를 방문할 때마다 돈을 벌게 된다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러 번 이용할 수도 있다.

입력

첫째 줄에 도시의 수 N과 시작 도시, 도착 도시 그리고 교통 수단의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에는 교통 수단의 정보가 주어진다. 교통 수단의 정보는 “시작 끝 가격”과 같은 형식이다. 마지막 줄에는 오민식이 각 도시에서 벌 수 있는 돈의 최댓값이 0번 도시부터 차례대로 주어진다.

N과 M은 50보다 작거나 같고, 돈의 최댓값과 교통 수단의 가격은 1,000,000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착했을 때 돈을 무한히 많이 가지고 있을 수 있다면 "Gee"를 출력한다.

---

벨만포드 알고리즘을 이용해 문제를 해결한다.

음수 사이클이 존재할 경우(무한 반복) 도착 도시도 무한대로 처리

 

#include <iostream>
#include <tuple>
#include <vector>
#include <limits.h>

using namespace std;

int main()
{
    // 'edge'라는 이름의 튜플 타입을 정의. (출발 도시, 도착 도시, 가격)
    typedef tuple<int, int, int> edge;

    // N: 도시의 수, M: 도로의 수, startCity: 시작 도시, endCity: 목적 도시
    int N, M, startCity, endCity;

    // mDistance: 각 도시에 도달할 수 있는 최대 금액을 저장하는 벡터
    // cityMoney: 각 도시에 있는 돈을 저장하는 벡터
    vector<long> mDistance, cityMoney;

    // edges: 각 도로의 정보를 저장하는 벡터 (출발 도시, 도착 도시, 도로의 가격)
    vector<edge> edges;

   
    cin >> N >> startCity >> endCity >> M;

   
    mDistance.resize(N);
    cityMoney.resize(N);

    // mDistance는 처음에 모두 최소값으로 설정 (아직 도달할 수 없는 상태)
    fill(mDistance.begin(), mDistance.end(), LONG_MIN);

   
    for (int i = 0; i < M; i++)
    {
        int s, e, p;
        cin >> s >> e >> p;
        edges.push_back(make_tuple(s, e, p));
    }

  
    for (int i = 0; i < N; i++)
    {
        cin >> cityMoney[i];
    }

    // 시작 도시에는 그 도시의 금액을 초기화
    mDistance[startCity] = cityMoney[startCity];

    // 벨만-포드 알고리즘 수행 (최대 N+50번 반복)
    for (int i = 0; i <= N + 50; i++)
    {
        // 모든 도로를 한 번씩 순회하면서 최댓값 갱신
        for (int j = 0; j < M; j++)
        {
            int start = get<0>(edges[j]);  // 도로의 출발 도시
            int end = get<1>(edges[j]);    // 도로의 도착 도시
            int price = get<2>(edges[j]);  // 도로를 이용하는 비용

            // 출발 도시의 금액이 아직 도달할 수 없으면 무시
            if (mDistance[start] == LONG_MIN)
            {
                continue;
            }
            // 출발 도시가 무한대에 도달한 경우, 도착 도시도 무한대 처리
            else if (mDistance[start] == LONG_MAX)
            {
                mDistance[end] = LONG_MAX;
            }
            // 도착 도시의 금액을 갱신 (출발 도시의 금액 + 도착 도시의 돈 - 도로 비용)
            else if (mDistance[end] < mDistance[start] + cityMoney[end] - price)
            {
                mDistance[end] = mDistance[start] + cityMoney[end] - price;

                // N번째 반복 후에도 값이 갱신되면 음수 사이클이 존재하는 것
                if (i >= N - 1)
                {
                    mDistance[end] = LONG_MAX;
                }
            }
        }
    }

   
    if (mDistance[endCity] == LONG_MIN)
    {
        // 목적 도시에 도달할 수 없으면 "gg" 출력
        cout << "gg";
    }
    else if (mDistance[endCity] == LONG_MAX)
    {
        // 목적 도시에 무한대 금액이 도달했으면 "Gee" 출력
        cout << "Gee";
    }
    else
    {
        cout << mDistance[endCity];
    }
}

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