infoarena

Aici puteţi discuta despre problema Sate (http://infoarena.ro/problema/sate).

Am vazut prin alte topicuri ca un BF iese din timp... daca e facut cu o coada alocata de la bun inceput nu sunt prob, fara parsare ;) ... eu cel putin nu la asta am probleme...

Ci primesc cate un WA la un singur test din grupuri... nu-mi prea dau seama ce cazuri de exceptie exista ... ???

Incearca pe teste de genul:


Raspunsul trebuie sa fie 10.

Multumesc frumos, acu da :) ... adica na, ca de obicei vechea greseala... citeste relatiile pana la n nu pana la m ...  :fool:

mie imi pica un test cu TLE si am implementat un O (N+M). voi ce tip de liste folositi, k eu am lucrat cu "vector <long>" din STL  :-k

Ai grija sa opresti cautarea (break, return) cand ai ajuns la solutie.

nop...nu de aici e problema...am conditiile bine puse..cred k e de la timpu de acces la lista

La problema asta nu e indicat sa folosesti STL. Merge mai greu decat alte modalitati de retinere a grafului. Incearca implementarea lui Radu Berinde cu vectori alocati dinamic: http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai

Mie mi'a intrat frumos cu liste. http://infoarena.ro/job_detail/133446
Acelasi algoritm, folosind STL iesea din timp pe un test.

Nu inteleg, eu reprezint problema cu un graf neorientat si retin si costurile de la nodul i la j, si mie imi da si pe foaie ca de la 1 la 11 , costul este 44. Unde gresesc?

Inseamna ca daca ai un drum de la x la y de costul c, cand parcurgi x -> y, trebuie sa aduni costul, iar cand parcurgi y -> x il scazi.
1->7   : +10
7->5   :  -4
5->8   :  +8
8->6   :  -5
6->4   :  -4
4->11 : +13
           ----
           +18

cred ca puteti sa folositi STL ptr ca merge foarte bine... http://infoarena.ro/job_detail/430808

Am folosit si queue( BFS) si vector( liste)

"trebuie determinata distanta intre satele X si Y, daca acest lucru este posibil."
"Intotdeauna va putea fi determinata distanta dintre X si Y pe baza informatiilor primite"

?

prin STL cred ca depinde de implementare si de mici optimizari.. de exemplu stiu ca cineva a luat 100 dupa ce a micsorat dimensiunea vectorilor cu 1 sau 2

btw.. eu inca sunt uimit ca functioneaza: job #482680 si are si un timp foarte bun. pe testul pe care luam TLE fac acum 52 ms (sursa mea: job #557996 )

Poate sa-mi explice si mie cineva care e problema cu testul 13 de iau TLE pe o implementare O(n+m) cu BFS,graf memorat prin liste de adiacenta alocate dinamic(nu cu STL),citire cu cstdio si conditie de oprire din BFS cand a gasit solutia?  ???

LE : Gata,am parsat citirea si am luat 100pct  :peacefingers: Mersi eudanip (http://"http://infoarena.ro/utilizator/eudanip")  :)

Parseaza citirea.

Ce poate avea solutia mea? Iau TLE pe un test. Oare din cauza ca nu parsez citirea?

Cod:

#include <fstream>
#include <vector>
#define Max 100100
using namespace std;

FILE *fin = fopen("sate.in", "r");
FILE *fout = fopen("sate.out", "w");

int n, m, i, j, k, ok, minim, maxim,z;
vector < int > v[Max];
int vizit[Max], dist[Max], p, u, x, y;

void bfs(int val){
    vizit[val] = 1;
    for(int i = 0; i < v[val].size(); i += 2){
        if(vizit[v[val]] == 0){
            dist[v[val]] = dist[val] + v[val][i + 1];
            bfs(v[val]);
        }
    }
    return;
}

void read(){
    fscanf(fin, "%d%d%d%d", &n, &m, &p, &u);
    for(i = 1; i <= m; i ++){
        fscanf(fin, "%d%d%d", &x, &y, &z);
        v

• .push_back(y);

        v

• .push_back(z);

        v[y].push_back(x);
        v[y].push_back(-z);
    }
    return;
}

int main(){
    read(); bfs(p);
    fprintf(fout, "%d", dist);
    return 0;
}

Ar trebui sa se garanteze ca X < Y sau sa se schimbe testele. Cu prima mea sursa daca X > Y, distanta afisata imi iesea negativa (am luat 100p). In plus, merge si cu DFS (sugerez un tag in plus).

DA :D :D :D