Hi all.
I'm trying to solve this problem using Floyd Warshall... but I'm getting lots of wrong answers...
I think the problem isn't with the floyd... but perhaps with the input....
I would apreciate if someone could give me some hint or input case that my program fails...
below is my code.
Code: Select all
#include <iostream>
#include <map>
#include <stdio.h>
#include <stdlib.h>
#define MAX_V 35
#define inf 0x3f3f3f3f
using namespace std;
double d[MAX_V][MAX_V];
void floyd_warshall(int N);
int main(void) {
int caso=1, npaises;
char msg[2][5];
strcpy(msg[0], "No");
strcpy(msg[1], "Yes");
while (scanf("%d\n", &npaises) && npaises != 0) {
int i, j, dest, qtd, nq, u, v;
double g[MAX_V][MAX_V];
double w;
bool res = 0;
char pais[100], pais1[100], pais2[100];
map<string, int> paises;
for (i=1; i<=MAX_V; i++)
for (j=1; j<=MAX_V; j++)
d[i][j] = 0;
for (i=1; i<=npaises; i++) {
scanf("%s", pais);
paises[string(pais)] = i;
}
scanf("%d\n", &nq);
for (i=1; i<=nq; i++) {
scanf("%s %lf %s\n", pais1, &w, pais2);
d[paises[string(pais1)]][paises[string(pais2)]] = w;
}
floyd_warshall(npaises);
for (i=1; i<=npaises; i++) {
if (d[i][i] > 1.00001) {
res = 1;
break;
}
}
printf("Case %d: %s\n", caso++, msg[res]);
}
return 0;
}
void floyd_warshall(int N) {
int i, j, k;
for (i=1; i<=N; i++) d[i][i] = 1.0;
for (k=1; k<=N; k++)
for (i=1; i<=N; i++)
for (j=1; j<=N; j++) {
d[i][j] = max(d[i][j], d[i][k] * d[k][j]);
}
}