백준 22358 스키장

 

UCPC 예선 H.

ABC를 풀고 나머지 문제 중에서 유일하게 풀이가 떠올랐는데, 결국 10트 하고 못 풀었다. 알고 보니 애초에 bfs나 다잌스트라로 풀 수 없는 문제였다. 오늘 공식 풀이를 보고도 한참 이해를 못 했고 점화식을 가져다 써서 AC는 받았지만 사실 아직도 이해를 못 한 것 같다. 

 

결과적으로 쉬운 3문제밖에 풀지 못한 결과가 너무 아쉽다.

10번이나 왜맞틀 하면서도 풀이가 틀렸다는 생각을 안 해본 게 바보 같다.

풀이를 보고도 이해를 못한 게 바보 같다. 

 

ps는 당분간 쉬어야겠다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

vector<pii> adj[100005], rev[100005];
ll dist[100005][11];
int n, m, K, S, T;

void input() {
    cin >> n >> m >> K >> S >> T;
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        rev[b].push_back({a, c});
    }
}

void d() {
    dist[T][0] = 0;
    for(int from = n; from >= 1; --from) {
        for(auto& [to, toDist] : adj[from]) {
            dist[from][0] = max(dist[from][0], dist[to][0] + toDist);
        }
    }
}

void dd(int k) {
    for(int from = n; from >= 1; --from) {
        for(auto& [to, toDist] : rev[from]) {
            dist[from][k] = max(dist[from][k], dist[to][k-1]);
        }
    }
    for(int from = n; from >= 1; --from) {
        for(auto& [to, toDist] : adj[from]) {
            dist[from][k] = max(dist[from][k], dist[to][k] + toDist);
        }
    }
}

int main() {
    fastio;
    input();
    memset(dist, 0xc0, sizeof(dist));
    
    d();
    for(int k = 1; k <= K; ++k) {
        dd(k);
    }

    ll ans = dist[S][0];
    for(int k = 1; k <= K; ++k) {
        ans = max(ans, dist[S][k]);
    }
    cout << (ans < 0 ? -1 : ans);
}