Array
(
)

ajuda problema Dijkstra

André Roberto
   - 24 nov 2008

não consegui resolver este problema que é implementado com Dijkstra.
será que poderiam me ajudar...

ai vai o link:http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1742

#include<iostream>
define MAXCST 999999999
define MAX 100

using namespace std;

int g[MAX][MAX], vertices;

int dijkstra(int origem, int destino){
int i, minimo, atual;
int passou[MAX], pred[MAX], custo[MAX];
for(i = 0; i < vertices; i++){
pred[i] = -1;
custo[i] = MAXCST;
passou[i] = 0;
}
custo[origem] = 0;
atual = origem;

while(atual != destino){
for(i = 0; i < vertices; i++){
if(custo[atual] + g[atual][i] < custo[i]){
custo[i] = custo[atual] + g[atual][i];
pred[i] = atual;
}
}
minimo = MAXCST;
passou[atual] = 1;
for(i = 0; i < vertices; i++){
if((custo[i] < minimo) && (!passou[i])){
minimo = custo[i];
atual = i;
}
}
//caso nao conseguiu ir para lugar algum saindo da origem
if(minimo == MAXCST){
return MAXCST;
}
//for(i = 0; i < vertices; i++){
// cout << pred[i] << ´ ´ << custo[i] << ´ ´ << passou[i] << endl;
//}
}
return custo[origem];

}
int main(){
int i, j, arestas, orig, dest, peso;
cin >> vertices >> arestas;

memset(g, 63, sizeof(g)); //1.061.109.567 (deve ser um pouco maior um igual a MAXCST)

for(i = 0; i < arestas; i++){
cin >> orig >> dest >> peso;
g[orig][dest] = peso;
}
cout << dijkstra(0,5) << endl << endl;
cout << dijkstra(0,1) << endl << endl;
cout << dijkstra(0,4) << endl << endl;
cout << dijkstra(0,2) << endl << endl;
return(0);
}