Sto provando a risolvere il problema Tax avoidance,il mio programma fa tutti i testcase corretti apparte il numero 10 e non riesco a capire cosa ci sia di sbagliato
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<vector<pair<int,double> > >adj(n);
int t1,t2,t3;
for(int i=0;i<m;i++)
{
cin>>t1>>t2>>t3;
adj[t1].push_back({t2,t3});
}
vector<double>dist(n);
vector<bool>vis(n);
int nodo1=-1,nodo2=-1;
double minimo=-1;
for(int j=0;j<n;j++)
{
priority_queue<pair<double,int> >coda;
for(int i=0;i<n;i++)
{
dist[i]=2000;
vis[i]=false;
}
dist[j]=0;
coda.push({0,j});
int s;
double val;
while(!coda.empty())
{
s=coda.top().second;
val=-coda.top().first;
coda.pop();
if(vis[s])continue;
vis[s]=true;
for(auto x: adj[s])
{
double tmp=(1000.0-val)*(x.second/1000.0)+val;
if(tmp<dist[x.first])
{
dist[x.first]=tmp;
coda.push({-tmp,x.first});
}
}
}
for(int i=0;i<n;i++)
{
if(i!=j&&dist[i]>minimo)
{
minimo=dist[i];
nodo1=j;
nodo2=i;
}
}
}
cout<<nodo1<<" "<<nodo2<<"\n";
}
La mia idea è quella di applicare l’algoritmo di Dijkstra ad ogni nodo per trovare l’ammontare minimo di tasse da pagare per andare dal nodo di partenza agli altri.
Come risultato stampo la coppia di nodi (A,B) tale che il numero di tasse minimo da pagare per andare da A a B sia il massimo possibile.