Ajuda problema triprouting

24/11/2008

1

Estou encontrando problemas pra resolver este programa, não consegui resolvelo ....
este é o link do problema...


[url]http://online-judge.uva.es/p/v1/186.html[/url]

#include<iostream>
include<iomanip>
include<map>
define INFINITO 999999999

using namespace std;

struct digraph {
int V;
int A;
int adj[301][301];
string rota[301][301];
};
/* Um objeto do tipo Digraph contém o endereço de um digraph. */
typedef struct digraph *Digraph;
void Floyd(Digraph G){
for(int k = 1; k <= G->V; k++){
for(int i = 1; i <= G->V; i++){
for(int j = 1; j <= G->V; j++){
if((G->adj[j][k] + G->adj[k][i] < G->adj[j][i])){
G->adj[j][i] = G->adj[j][k]+G->adj[k][i];
}
}
}
}
}

int main(void){
Digraph D = new (struct digraph);
map < string, int > mapa;
int i, j, pos, achou_or, achou_ds, arestas, custo;
string origem, saida;
string destino;
string s[5];
int tamanho = 0;
int aa, bb;
int cidades = 201;

cin >> cidades >> arestas;
for(i = 0; i < cidades+1; i++){
for(j = 0; j < cidades+1; j++){
D->adj[i][j]=INFINITO;
}
}
string x;
while(getline(cin, x)){
pos = 1;
for(i = 0; i < x.length(); i++){
if(x[i] != ´,´){
saida += x[i];
}else{
s[pos] = saida;
saida.clear();
pos++;
}

}
if(pos < 2) break;
s[pos] = saida;
saida.clear();
origem = s[1];
destino = s[2];
if(mapa.find(origem) != mapa.end()){
achou_or = mapa[origem];
}else{
mapa[origem] = ++tamanho;
achou_or = tamanho;
}
if(mapa.find(destino) != mapa.end()){
achou_or = mapa[destino];
}else{
mapa[destino] = ++tamanho;
achou_or = tamanho;
}
arestas += 1;
s[1].append(21 - s[1].length(), ´ ´);
s[2].append(21 - s[2].length(), ´ ´);
s[3].append(11 - s[3].length(), ´ ´);
if(s[4].length() < 6){
s[3].append(5 - s[4].length(), ´ ´);
}
if((atoi(s[4].c_str()) < D->adj[achou_or][achou_ds])){
D->rota[achou_or][achou_ds] = s[1] + s[2] + s[3] + s[4];
D->rota[achou_ds][achou_or] = s[1] + s[2] + s[3] + s[4];
D->adj[achou_or][achou_ds] = atoi(s[4].c_str());
D->adj[achou_ds][achou_or] = atoi(s[4].c_str());
}
Floyd(D);
while(getline(cin, x)){
pos = 1;
for(i = 1; i < D->V+1; i++){ // Mostra a Matriz de Adjascencia
for(j = 1; j < D->V+1; j++){
cout << setw(12) << D->adj[i][j] << ´ ´;
cout << endl;
}
}
aa = mapa[s[1]];
bb = mapa[s[2]];
cout << D->rota[aa][bb] << endl;
cout << D->adj[aa][bb] << endl;
}
}
return(0);
}[url][/url][/b]


Responder