여행 2157

문제

접근 방법

왼쪽에서 오른쪽으로 가는 방향만 입력받는다.
이후 1에서 N으로 탐색을 시도해 준다. 같은 위치에서 같은 횟수로 왔는데 값이 더 작다면 무시하면 된다.
만약 M만큼 사용했는데도 도착 안 했다면 그 뒤에 값은 무시하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pip; // 기내식 점수, 횟수, 마을 번호
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, K, ret = 0;
    cin >> N >> M >> K;
    vector<vector<pii>> graph(N + 1, vector<pii>());
    vector<vector<int>> visted(M + 1, vector<int>(N + 1, -1));
    for (int i = 0, a, b, c; i < K; ++i)
    {
        cin >> a >> b >> c;
        if (a > b)
            continue;
        graph[a].push_back({b, c});
    }
    queue<pip> q;
    q.push({0, {1, 1}});
    visted[1][1] = 0;
    while (!q.empty())
    {
        pip cur = q.front();
        q.pop();
        int cnt = cur.second.first;
        if (visted[cnt][cur.second.second] > cur.first || cur.second.first == M)
            continue;
        for (pii next : graph[cur.second.second])
        {
            int nextScore = cur.first + next.second;
            if (visted[cnt + 1][next.first] >= nextScore)
                continue;
            visted[cnt + 1][next.first] = nextScore;
            q.push({nextScore, {cnt + 1, next.first}});
        }
    }
    for (int i = 1; i <= M; ++i)
        ret = visted[i][N] > ret ? visted[i][N] : ret;
    cout << ret;
    return 0;
}

풀이

M개 이하로 도착해야 하기에 당장 앞에 이익을 무시하고 더 멀리 가는 것이 이득일 경우도 존재한다.

그렇기에 기내식 점수를 저장해 줄 때 횟수도 인덱스로 사용해 주면 좋다.