14619 섬 여행

dp문제.

A위치에서 다리 K개를 건넜을 때 도착할 수 있는 섬의 높이 중에 가장 작은값을 출력하면 된다.

d[x][c] = 현재 위치가 x이고 c개의 다리를 더 건널 수 있을 때 도달가능한 가장 낮은 높이.

<코드>

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
int n, m, t, a[101], s, k, d[101][501];
vector<int> v[101];
 
int dfs(int x, int c) {
    if (d[x][c] != -1) return d[x][c];
    if (!c) return a[x];
    d[x][c] = 2e9;
    for (auto i : v[x]) d[x][c] = min(d[x][c], dfs(i, c - 1));
    return d[x][c];
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    while (m--) {
        int b, c;
        scanf("%d%d", &b, &c);
        v[b].push_back(c);
        v[c].push_back(b);
    }
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &s, &k);
        // s위치에 간선이 존재하지 않는다면 k(>=1)번 움직이는게 불가능하다
        printf("%d\n", v[s].size() ? dfs(s, k) : -1);
    }
    return 0;
}