여행 C++ - 백준 2157

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

DP 문제.

문제 접근

간선의 개수가 최대 $1e5$이기 때문에 깡 BFS를 돌리면 결과는 TLE다.

따라서 가능한 경우를 탐색하면서도 TLE가 나지 않는

다른 방법인 DP를 사용해야 한다.

$DP(i,j)$ 를 도시 $i$개를 지나며 $j$로 끝나는 여행 경로의

기내식 점수의 최댓값이라고 하자.

그러면 다음과 같은 점화식을 얻을 수 있다.

$DP(i,j)=DP(i-1,k)+cost(k,j)$ (단, $k$와 $j$ 사이에는 항로가 있다)

이를 구현한 코드는 다음과 같다.

나이브하게 삼중포문을 돌아도 약 86ms정도 소요된다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> dp(m,vector<int> (n,-1)),cost(n,vector<int> (n,-1));
    for(int i=0;i<k;i++){
        int a,b,c;
        cin >> a >> b >> c;
        if(a>b) continue;
        cost[a][b]=max(cost[(--a)][(--b)],c);
    }
    dp[0][0]=0;
    for(int i=1;i<m;i++) for(int j=0;j<n;j++) for(int k=0;k<j;k++){
        if(cost[k][j]!=-1 && dp[i-1][k]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][k]+cost[k][j]);
    }
    int ans=0;
    for(int i=1;i<m;i++) ans=max(ans,dp[i][n-1]);
    cout << ans;
    return 0;
}