461 Sate

[•DITzoneC]

Aici puteţi discuta despre problema Sate.

[•sima_cotizo]

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 ...

[•filipb]

Incearca pe teste de genul:

Cod:

1000 4 5 10 
1 3 10
3 5 10
10 20 70
1 20 100

Raspunsul trebuie sa fie 10.

[•sima_cotizo]

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

[•bogdanhm999]

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 

[•Dastas]

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

[•bogdanhm999]

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

[•wefgef]

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

[•gabitzish1]

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

[•popoiu.george]

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?

[•gabitzish1]

Satele sunt asezate in ordine, de la stanga la dreapta, conform numerelor care le identifica.

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

[•dushmi]

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)

[•Bit_Master]

"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"

?

[•tinky]

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 )

[•scipianus]

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  Mersi eudanip 

[•eudanip]

Parseaza citirea.

[•StarGold2]

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;
}

[•oldatlantian]

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).

[•Pera]

DA