Nu știu care este problem la rezolvarea mea: Am încercat cu ideea lui Filip
Eu am facut un pic altfel ( de fapt e acelasi lucru cu solutia oficiala dar e formulat altfel ):
* pentru fiecare pereche (i j) trebuie sa am A[ i ][ j ] <= A[ i ][ k ] + A[ k ][ j ] pentru orice k. Daca exista un k pt. care A[ i ][ k ] + A[ k ][ j ] < A[ i ][ j ] => nu am solutie
* daca exista o pereche (i j) pt. care nu exista nici un k a. i. A[ i ][ j ] = A[ i ][ k ] + A[ k ][ j ] si nu am muchie de la i la j in graf => nu am solutie
Eu am facut asa si am obtinut 100
.
Și am mi-a rezultat asa:
# include <cstdio>
# include <cstring>
using namespace std;
FILE *f=fopen("rfinv.in","r"),*g=fopen("rfinv.out","w");
short n,m,t,i,j;
bool A[51][51],C[51][51];int B[51][51];
/*
A matrice de adiacenta in care A
[j]=1 daca exista legatura intre i si j si 0 altfel
C matrice in care salvez 1 daca exista drum intre i si j sau costul dintre i si j poate fi descompus pe drumul i->k k->j
B matricea unde se afla rezultatul royfloyd din fisier
*/
bool royfloyd()
{
short i,j,k;
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j)
{
if(B[j] > B[k]+B[k][j])
return 0;
if(A[j] || B[j]==B[k]+B[k][j])
C[j]=1;
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j)
if(!C[j])//daca exista drum si nu nu este pe diag princ
return 0;
return 1;
}
template<class T>
void initMatrice(T A[][51])
{
for(i=0;i<n;++i)
memset(A,0,(n+1)*sizeof(T));
}
int main()
{
fscanf(f,"%hd",&t);
while(t--)
{
fscanf(f,"%hd %hd\n",&n,&m);
initMatrice(A);
initMatrice(B);
initMatrice(C);
short x,y;
for(i=0;i<m;++i)
{
fscanf(f,"%hd %hd\n",&x,&y);
A }
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
fscanf(f,"%d",B+j);
if(royfloyd())
fprintf(g,"DA\n");
else
fprintf(g,"NU\n");
}
}
Primesc mesajul Incorect