Per risolvere questo problema ho applicato l’algoritmo di dijkstra per trovare il ciclo minore. Riesco a risolvere soltato 4 casi su 10.
Questo è il codice:
#include <iostream>
#include <fstream>
#include <climits>
#include <queue>
using namespace std;
struct nodo
{
long long min = LONG_MAX;
vector<pair<int, int>> connessi;
};
int N, M;
nodo nodi[1000000];
int da[20000], a[20000], w[20000];
int dijkstra(int da, int a, int w)
{
queue<int> coda;
coda.push(da);
nodi[da].min = 0;
while(!coda.empty())
{
int attuale = coda.front();
coda.pop();
for(auto i: nodi[attuale].connessi)
{
if(attuale == da && i.first == a)
continue;
if(i.second + nodi[attuale].min < nodi[i.first].min)
{
nodi[i.first].min = i.second + nodi[attuale].min;
coda.push(i.first);
}
}
}
return nodi[a].min + w;
}
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
in >> N >> M;
for(int i = 0; i < M; i++)
{
in >> da[i] >> a[i] >> w[i];
nodi[da[i]].connessi.push_back(pair<int, int>(a[i],w[i]));
nodi[a[i]].connessi.push_back(pair<int, int>(da[i],w[i]));
}
int minore = 1000000;
for(int i = 0; i < N; i++)
{
int d = dijkstra(da[i], a[i], w[i]);
if(d < minore)
minore = d;
for(int i = 1; i <= N; i++)
nodi[i].min = LONG_MAX;
}
out << minore;
}