제출 #1202699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202699		SSKMF	Museum (CEOI17_museum)	C++20	20 / 100	3093 ms	18592 KiB

museum

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

vector < pair <int , int> > adiacenta[10001];
vector <int> minim[10001][2];

inline void Parcurgere (const int nod , const int sursa)
{
    minim[nod][0].resize(2);
    minim[nod][1].resize(2);

    for (auto vecin : adiacenta[nod]) {
        if (vecin.first != sursa)
        {
            Parcurgere(vecin.first , nod);

            minim[nod][0].resize((int)minim[nod][0].size() + (int)minim[vecin.first][0].size() - 1 , 1000000000);
            minim[nod][1].resize((int)minim[nod][1].size() + (int)minim[vecin.first][1].size() - 1 , 1000000000);

            for (int total = (int)minim[nod][1].size() - 1 ; total > 1 ; total--) {
                for (int termen = min(total - 1 , (int)minim[vecin.first][1].size() - 1) ; termen ; termen--) 
                    { minim[nod][1][total] = min({minim[nod][1][total] , minim[nod][1][total - termen] + minim[vecin.first][0][termen] + 2 * vecin.second , minim[nod][0][total - termen] + minim[vecin.first][1][termen] + vecin.second}); }
            }

            for (int total = (int)minim[nod][0].size() - 1 ; total > 1 ; total--) {
                for (int termen = min(total - 1 , (int)minim[vecin.first][0].size() - 1) ; termen ; termen--) 
                    { minim[nod][0][total] = min(minim[nod][0][total] , minim[nod][0][total - termen] + minim[vecin.first][0][termen] + 2 * vecin.second); }
            }
        }
    }
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri , dorit , inceput;
    cin >> numar_noduri >> dorit >> inceput;

    for (int indice = 1 ; indice < numar_noduri ; indice++)
    {
        int nod[2] , cost;
        cin >> nod[0] >> nod[1] >> cost;
        adiacenta[nod[0]].push_back({nod[1] , cost});
        adiacenta[nod[1]].push_back({nod[0] , cost});
    }

    Parcurgere(inceput , 0);
    
    cout << minim[inceput][1][dorit];
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20