Leaderboard

Ce-mi iese?:> La rose Vincent Drux - Siegfried de Turckheim Download

Solutia naiva ar fi sa faci un backtracking pe parcurgeri in adancime si la depasirea timpului sa actualizezi maximul, oricum iese cu mult din timp. O solutie mai buna ar fi o dinamica in T*N unde D[j] pastreaza cele mai bune rezultate ale vecinilor lui j plecand de la momentul de timp i. Toate bune si frumoase pana a aparut problema in care trebuie sa-ti dai seama daca ai mai vizitat sau nu vecinul k al lui j in lantul i (corespunzator momentului de timp) si ca sa faci asta trebuie sa mai faci inca i-1 verificari ceea ce ducea la un timp T!*N si memorie T*N. Asa ca m-am gandit sa memorez fiecare configuratie/drum/lant in functie de fiecare moment de timp dependent de nodul cu pricina si ajungeam la un timp mai bun T*N^2 dar memoria ajungea si ea la fel, iar la datele din problema in cel mai rau caz la 600 de noduri se ocupau cam 5 gb in ram asa ca am limitat nodurile la 100 si avem memoria maxima de 200mb (cam mare) dar timpul maxim de 5 sutimi . Multumesc lui bylosul93 pentru inspiratie si acum codul: Ideone.com | Online C++ Compiler & Debugging Tool #include <cstdio> #include <iostream> #include <vector> using namespace std; const int T = 5001, N = 101; int maxMoney, startNode, nodes, edges, time, win[N], mat[T][N][N]; vector<vector<pair<int, int> > > adjacent; void parse_input() { cin >> nodes >> edges >> startNode >> time; for (int i = 1; i <= nodes; ++i) cin >> win[i]; // money gain for node i adjacent.resize(nodes + 1); for (int i = 0; i < edges; ++i) { int t, x, y; cin >> t >> x >> y; // t time between x and y adjacent[x].push_back(make_pair(y, t)); adjacent[y].push_back(make_pair(x, t)); } } void solve() { /** O(TN^2) */ maxMoney = win[startNode]; // atribuim maximului castigul de start mat[0][startNode][0] = maxMoney; // la momentul de timp t=0 initializam nodul de start mat[0][startNode][startNode] = 1; // marcam ca este vizitat in lantul curent for (int i = 0; i < time; ++i) { // pentru fiecare moment de timp for (int j = 1; j <= nodes; ++j) { // luam fiecare nod if (mat[i][j][0]) { // si daca s-a putut ajunge in el (avand suma strict pozitiva) for (int k = 0; k < adjacent[j].size(); ++k) { // luam fiecare vecin al lui int tmpTime = i + adjacent[j][k].second; // aflam noul timp pentru vizita vecinului int tmpMoney = mat[i][j][0]; // clonam suma de la care pornim vizita if (!mat[i][j][adjacent[j][k].first]) { // daca nu a mai fost vizitat acel vecin tmpMoney += win[adjacent[j][k].first]; // actualizam suma } // apoi daca vizita intra in timp si obtinem o suma mai buna de bani if (tmpTime <= time && tmpMoney > mat[tmpTime][adjacent[j][k].first][0]) { if (tmpMoney > maxMoney) maxMoney = tmpMoney; // actualizam maximul mat[tmpTime][adjacent[j][k].first][0] = tmpMoney; // evenimentul in matrice for (int l = 1; l <= nodes; ++l) { // dar si lantul de noduri vizitate mat[tmpTime][adjacent[j][k].first][l] = mat[i][j][l]; mat[tmpTime][adjacent[j][k].first][adjacent[j][k].first] = 1; } } } } } } } int main() { freopen("dp_graf.in", "rt", stdin); // switch input source parse_input(); solve(); cout << maxMoney; return 0; } Mai merge scazut si din T, oricum in implementarea ta nu cred ca folosesti dimensiuni asa mari.