Ho fatto quest’algoritmo, e tutti i testcase tranne uno, il numero 10, vanno:
cin>>n>>m;
vector<pair<int, float>> adj[n]; //adj[nodo attuale] = {nodo di arrivo, peso}
for(int i = 0; i < m; ++i){
int a, b; float w; cin >> a >> b >> w;
adj[a].push_back({b, w});
}
pi best = {0, 0};
float best_saldo = 1000;
for(int i = 0; i < n; ++i){
vector<float> saldo(n, 0);
priority_queue<pair<float, int>> q; //{-distanza, nodo di arrivo}
vector<bool> processed(n, false);
saldo[i] = 1000; // saldo[nodo di partenza] = 0
q.push({1000, i});
while (!q.empty()) {
int a = q.top().second; q.pop();
if (processed[a]) continue;
processed[a] = true;
for (auto u : adj[a]) {
int b = u.first; float w = u.second;
if (saldo[a] * ((float)1 - w / (float)1000) > saldo[b]) {
saldo[b] = saldo[a] * ((float)1 - w / (float)1000);
q.push({saldo[b], b});
}
}
}
for(int j = 0; j < n; ++j){
if(saldo[j] < best_saldo){
best = {i, j};
best_saldo = saldo[j];
}
}
}
cout << best.first << " " << best.second << endl;
return 0;
}
l’algoritmo è semplicemente l’algoritmo di dijkstra ripetuto per ogni nodo, e mi trovo la soluzione in questo modo. Tranne per quell’unico testcase. Chiedo aiuto.