17242 - Kaka & Bebe

step 1

$dp[i][j]$ = i번째 정점에 있고 지금까지 Kaka를 j마리를 봤을 때 그때까지 볼 수 있는 Bebe의 최소 마리 수

를 구합니다.

step 2

위 dp를 구해봅시다. 모든 간선마다 Kaka와 Bebe가 한 마리씩은 있기 때문에 $dp[i][j]$는 $dp[k][l](l>j)$에만 영향을 미칠 수 있습니다. 즉, $j$가 작은 $dp$부터 출발해서 순서대로 채워주면 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int, pair<int, int>>> v[2000];
priority_queue<pair<int, int>> q;
int dp[2000][2000],ch[2000][2000];
int main() {
    int n, m, i, j;
    scanf("%d%d", &n, &m);
    for (i = 1;i <= m;i++) {
        int x, y, z, w;
        scanf("%d%d%d%d", &x, &y, &z, &w);
        v[x].push_back({ y,{z,w} });
        v[y].push_back({ x,{z,w} });
    }
    for (i = 0;i <= n;i++) {
        for (j = 0;j <= 1000;j++) dp[i][j] = 10000;
    }
    q.push({ 0,0 });
    dp[0][0] = 0;
    while (q.size()) {
        int c = q.top().first;
        int i = q.top().second;
        q.pop();
        if (ch[i][c] == 1) continue;
        ch[i][c] = 1;
        for (j = 0;j < v[i].size();j++) {
            if (c + v[i][j].second.first > 1000) continue;
            if (dp[i][c] + v[i][j].second.second > 1000) continue;
            if (dp[v[i][j].first][c + v[i][j].second.first] > dp[i][c] + v[i][j].second.second) {
                dp[v[i][j].first][c + v[i][j].second.first] = dp[i][c] + v[i][j].second.second;
                q.push({ c + v[i][j].second.first , v[i][j].first });
            }
        }
    }
    int val = 2100000000;
    for (i = 0;i <= 1000;i++) {
        if (dp[n - 1][i] == 10000) continue;
        if (val > i * dp[n - 1][i]) val = i * dp[n - 1][i];
    }
    printf("%d", (val == 2100000000 ? -1 : val));
    return 0;
}