Tax : non capisco il problema dell'algoritmo

Aiuto
1

l’idea era quella di usare l’algoritmo di floyd-warshall per calcolare tutte le tasse minime e prendere poi quella massima. Il programma sta nei tempi ma non negli output. Dipende dalla dimensione dei double o è un problema di algoritmo?

    #include<bits/stdc++.h>
    using namespace std;
    
    double mat[300][300];
    int main()
    {
        int N,M,a,b,c;
        cin>>N>>M;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
                mat[i][j]=0;
        
            mat[i][i]=1000;
        }
        for(int i=0;i<M;i++)
        {
            cin>>a>>b>>c;
            mat[a][b]=1000-c;
        }
        int mx=10001,I,J;
        for(int k=0;k<N;k++)
            for(int i=0;i<N;i++)
                for(int j=0;j<N;j++)
                {
                    if(mat[i][j]<mat[i][k]*mat[k][j]/1000)
                    {
    			mat[i][j]=mat[i][k]*mat[k][j]/1000;
    					
                    }
                }
           for(int i=0;i<N;i++)
           {
     		    for(int j=0;j<N;j++)
    		    {
    	            if(mat[i][j]<mx)
    	            {
    	                I=i;
    	                J=j;
    	                mx=mat[i][j];
    	            }
    		}
    	}
        cout<<I<<' '<<J;  
    }

edit:ho provato a rappresentare i valori di tasse come frazioni, semplificandole con l’MCD ma i subtask sono peggiorati sul tempo (1 sfora il tl) e sulla correttezza dell’output

3

ho capito il problema. semplicemente non si può usare floyd warshall moltiplicando i pesi, ma si deve ricondurre le moltiplicazioni a somme di logaritmi

4

io invece sono riuscito a farlo con floyd warshall moltiplicando i pesi :confused:

`for 
    for
      for  
         if (graph[i][k] * graph[k][j] > graph[i][j])
                graph[i][j] = graph[i][k] * graph[k][j];`

Solo che non devi salvare il peso così com’è ma farci una piccola modifica :stuck_out_tongue: