Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Problema lanturi  (Citit de 12424 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
AlexandruValeanu
Vorbaret
****

Karma: 29
Deconectat Deconectat

Mesaje: 167



Vezi Profilul
« : Ianuarie 10, 2013, 12:59:36 »

Am si eu nevoie de ceva ajutor la problema:
http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1004

Am nevoie de o indicatie de cum sa aflu toate drumurile de cost minim intre x si y.
Cred ca gresesc in functia rez dar nu imi dau seama cum sa corectez.

Cod:

#include <iostream>
#include <cstdio>

#define Nmax 1001
#define inf 0x3f3f3f3f

using namespace std;

int cost[Nmax][Nmax];
int nr[Nmax];
bool viz[Nmax];
int d[Nmax];
int tata[Nmax];

int n, m, inceput, sfarsit;
int a, b, c;
int coada[Nmax];
int inc, sf;

void citire(){

    FILE *f = fopen("lanturi.in", "r");

    fscanf(f,"%d %d %d %d", &n, &m, &inceput, &sfarsit);

    for(int i=1; i<=m; i++){

        fscanf(f,"%d %d %d", &a, &b, &c);

        cost[a][b] = cost[b][a] = c;
    }

    fclose(f);
}

void init(){

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(cost[i][j]==0)
                cost[i][j] = inf;

    for(int i=1; i<=n; i++){

      viz[i]=0;

      d[i] = cost[inceput][i];

      if(d[i] < inf)
            tata[i]= inceput;
      else
        tata[i] = 0;
    }

  viz[inceput]=1; tata[inceput]=0; d[inceput]=0;

}

void dijkstra(){

    int k = 1, min;

    for(int i=1; i<n; i++){

        min = inf;

        for(int i=1; i<=n; i++)
            if(viz[i]==0 && d[i]<min)
                min = d[i], k = i;

        coada[sf++] = k;

        viz[k] = 1;

        for(int i=1; i<=n; i++)
            if(viz[i]==0 && cost[k][i] + d[k] < d[i])
                d[i] = cost[k][i] + d[k], tata[i] = k;
    }
}

void rez(){

    for(int i=inc ; i<sf; i++)
        for(int j=1; j<=n; j++)
            if(cost[coada[i]][j] < inf)
                if(d[j] == d[coada[i]] + cost[coada[i]][j])
                    nr[coada[i]]++, nr[j]++;

}

void afis(){

    FILE *g = fopen("lanturi.out","w");

    fprintf(g,"%d\n", nr[sfarsit]);

    fclose(g);
}

int main()
{
    citire();
    init();
    dijkstra();
    rez();
    afis();

    return 0;
}

Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines